# Pisano periods of fibonacci mod

The wikipedia article on Pisano periods utilises the Binet's formula and quadratic residues to find $f(n)$ such that $F_n=f(n) \pmod{p}$ where $p$ is a prime number and $F_n$ is a Fibonacci number.

It turns out for $p=11$, $f(k)=3.(8^k-4^k)$. Now, given a constant $c$, can we check if there is a solution to $f(k)=c \pmod{11}$. Listing down all the possible remainders is an obvious choice, is there any other approach?

By Euler's Theorem,

$8^{10} \equiv 4^{10} \equiv 1 (mod 11)$

So, $3(8^{k+10}-4^{k+10}) \equiv 3(8^{k}-4^{k})(mod 11)$

Thus, f(k) has a periodicity of 10 such that

$f(k+10) \equiv f(k) (mod 11)$

Thus, if there's an integer $i (0 \le i \le 9)$ such that

$f(i) \equiv c (mod 11)$,

$i+10\mathbb{N}$ is the solution of the given equation.

Thus, we have no way to solve this question other than checking 10 possibilities.

• Is there some way by which we can eliminate the possibility of solution for some c. I mean if I were to calculate f(k) for larger values of k, and given a c, there are some c for which no k exists such that f(k)%p=c. Given a c can we atleast decide whether or not it'll have a solution.I'm not worried about "finding" the solution, just looking to eliminate some c. – sudeepdino008 Oct 9 '13 at 5:01