Question: Prove or disprove that if $m$, $n$ aren’t successive Fibonacci numbers, then $$F_k\equiv m\pmod{p},$$ $$F_{k+1}\equiv n\pmod{p}$$ has solutions for only finitely many primes $p$.

This is a spin-off of Coprimality of certain linear combinations of Fibonacci numbers (integer coefficients). The question at hand asks for integers $m$ and $n$ that make a certain expression always coprime. After meddling a bit with it, I found that the problem (in the case $c=1$) was equivalent to proving the existence of $m$, $n$ such that the above congruences didn’t have solutions for any prime. This problem seemed to have no clear attack route. But numerical tests suggested a similar and seemingly more friendly statement held: the above problem.

Despite being elementary to state, I’m at a total loss. I’ve tried playing with GCDs, but that brings me back to the original problem. I’ve tried to impose stricter conditions based on these congruences but found nothing. I’ve tried working with the$\bmod{p}$ analog of Binet’s Formula, but it looks hopelessly messy to manipulate both expressions simultaneously. Not to mention the uncomfortable $p\equiv3\pmod{10}$ case.

Weirdly enough, even though I’ve tried this for a while, I can’t even convince myself that it should be true. Assuming that the length of the $n$-th Pisano period grows like $O(n)$, and that the successive congruences in each are essentially random (which are assumptions that correspond with my intuition, but could possibly be false), we should expect $$\sum_{p\in\mathbb{P}}\frac{1}{p}=\infty$$ primes to have solutions. But again, setting (small) specific values for $m$, $n$ and manually calculating $\gcd(F_k-m,F_{k+1}-n)$ for a few hundred $k$, it seems that only (small) specific primes can appear. Maybe there’s something I’m missing, but I can’t prove anything either way.


In the following solution, all congruences are$\bmod{p}$.

Suppose $F_k\equiv m$, $F_{k+1}\equiv n$. Now, keep subtracting the equations. Then, $$F_{k-1}\equiv-(m-n)$$ $$F_{k-2}\equiv(2m-n)$$ $$F_{k-3}\equiv-(3m-2n)$$ $$F_{k-4}\equiv(5m-3n)$$ $$\vdots$$ $$F_1\equiv (-1)^{k-1}\left(F_km-F_{k-1}n\right).$$

Since $F_k\equiv m$ and $F_{k+1}\equiv n$, $F_{k-1}\equiv(n-m)$. We also know that $F_1=1$. We can therefore substitute to get $$m^2-(n-m)n\equiv (-1)^{k-1},$$ which is clearly impossible for large $p$. Unless, of course, $$\left|m^2-(n-m)n\right|=1.\tag{1}\label{1}$$ In other words, the original set of congruences has solutions for finitely many $p$, as long as $\eqref{1}$ does not hold.

Note that $\eqref{1}$ is true for successive Fibonacci numbers $m$ and $n$, by a simple proof by induction. In fact, $\eqref{1}$ holds precisely when $m$, $n$ are either successive Fibonacci numbers, or their negatives. This is essentially equivalent to P. 3 from the 1981 IMO, and is proven here.

  • $\begingroup$ It seems complete, who could have thought it would be as easy as that? Thanks! $\endgroup$
    – ViHdzP
    Nov 16 '19 at 16:11
  • $\begingroup$ By the way, I extended your answer a bit. I hope that that isn't a problem ;) $\endgroup$
    – ViHdzP
    Nov 16 '19 at 20:26
  • $\begingroup$ No problem, thanks $\endgroup$
    – aman
    Nov 17 '19 at 3:31

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.