2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – sudeepdino008 Oct 9 '13 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.