# Does every prime divide some Fibonacci number?

I am tring to show that $\forall a \in \Bbb P\; \exists n\in\Bbb N : a|F_n$, where $F$ is the fibonacci sequence defined as $\{F_n\}:F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$ $(n=2,3,...)$. How can I do this?

Originally, I was trying to show that $\forall a\in\Bbb N\;\exists n\in\Bbb N:a|F_n$. I soon found out that if the $k$-th Fibonacci can be divided by $m$, then the $nk$-th Fibonacci can also be divided by $m$, and this can be reduced to my original problem in this post.

-
By the way, the Fibonacci numbers (under the usual convention as you have, i.e. $F_0 = 0$ and $F_1 = 1$) form a "strong divisibility sequence": they satisfy the property that $F_{\gcd(m, n)} = \gcd(F_m, F_n)$. This explains your observation that if $m$ divides $F_k$, then $m$ divides $F_{nk}$ as well, because in fact $F_k$ divides $F_{nk}$. –  ShreevatsaR Mar 2 '14 at 9:31
Two more interesting facts: first, if $p \mid F_k$, then $\operatorname{ord}_p F_{kn}=\operatorname{ord}_p F_k + \operatorname{ord}_p n$. So if we find the first Fibonacci number divisible by $p$, we can easily say how many powers of $p$ divide any given Fibonacci number. Also, there are no known primes for which $p\mid F_k \implies p^2\mid F_k$, but it is conjectured that there are infinitely many. –  Slade Mar 2 '14 at 19:17

Yes. Consider any prime $p$. (Actually we don't need $p$ to be prime; consider any nonzero number $p$.)

You can of course take $F_0 = 0$ which is divisible by $p$, but let's suppose you want some $n > 1$ such that $F_n$ is divisible by $p$. Consider the Fibonacci sequence modulo $p$; call it $F'$.

That is, you have $F'_0 = 0$, $F'_1 = 1$, and for $n \ge 0$, you have $F'_{n+2} \equiv F'_{n+1} + F'_n \mod p$.

Now, there are only $p^2$ possible pairs of remainders $(F'_k, F'_{k+1})$, so some pair of consecutive remainders must occur again at some point. Further, the future of the sequence is entirely determined by its value at some two consecutive indices, so the sequence must itself repeat after that point. And it cannot go into some cycle that does not include $(F'_0, F'_1)$, because we can also work the sequence backwards: we can find $F'_{k-1}$ using $F'_{k-1} \equiv F'_{k+1} - F'_{k} \mod p$, etc.

This means that there always exists some $n > 0$ such that $F'_n \equiv F_0 \equiv 0 \mod p$ and $F'_{n+1} \equiv F_1 \equiv 1 \mod p$. Such an $n$ will do. This is called the period of the sequence modulo $p$ (or the $p$th Pisano period; of course some smaller $n$ may also exist (for which $F'_{n+1} \not\equiv 1 \mod p$).

-
can you elaborate on "And it cannot go into some cycle that does not include $(F′_0,F′_1)$, because we can also work the sequence backwards"? if the sequence (mod 5) is always $1,3,1,3,1,3...$ I can very well traverse it backwards but will never reach $0$ nonetheless. –  example Mar 3 '14 at 0:54
@example: Note I said $(F'_0,F'_1)$, not $(0,1)$ (which happens to be here our initial values, but that's not the argument). The argument is this: the eventual cycle can't be something that avoids the initial values. If you know that eventually the sequence becomes some $\dots,a,b,\dots,y,z,a,b,\dots,y,z,a,b\dots,y,z,\dots$, then you can trace the values backwards, and conclude that even the earlier terms (and in particular the first two terms) must also be the same as those in the cycle. There is only one way to reach any pair, so $(F'_0,F'_1)$, whatever they are, must be part of the cycle. –  ShreevatsaR Mar 3 '14 at 2:03
that cleared it up. thanks =) –  example Mar 3 '14 at 11:14
You have reinvented the wheel (cycle). @example See this post for the essence of the matter. –  Bill Dubuque Mar 6 '14 at 16:25

According to the Wikipedia article on Fibonacci numbers if $p$ is a prime number then

$$F_{p - \left(\frac{p}{5}\right)} \equiv 0 \text{ (mod } p)$$

where $\left(\frac{p}{5}\right)$ is the Legendre symbol.

$$\left(\frac{p}{5}\right) = \begin{cases} 0 & \textrm{if}\;p =5\\ 1 &\textrm{if}\;p \equiv \pm1 \pmod 5\\ -1 &\textrm{if}\;p \equiv \pm2 \pmod 5.\end{cases}$$

For example, if $p = 31$ then $F_{30} = 832040 = 2^3 \times 5 \times 11 \times 31 \times 61$.

The reference given is Lemmermeyer (2000), pp. 73–4.

-
Worth noting that this does not produce a good primality test on its own because Fibonnaci pseudoprimes also satisfy the above condition (there is significant overlap with Frobenius pseudoprimes as well due to the fact that the Frobenius test uses the $x^2 - x - 1$ quadratic). Just throwing it out there for people who might be wondering. –  Thomas Mar 2 '14 at 19:37
This congruence can actually be generalized by multiplying both the index and modulus by $p^{n-1}$. –  Jaycob Coleman Feb 15 at 23:40

We can in fact show a stronger statement with some algebraic number theory: If $p>5$ is prime then $p|F_{p\pm 1}$ for some choice of $+$ or $-$.

Suppose $\left(\frac{5}{p}\right)=1$. In this case, $p$ splits in $\mathbf{Z}\left[\frac{1+\sqrt{5}}{2}\right]=\mathbf{Z}[\varphi]$. Thus, we can write $p=\pm\pi\bar\pi$, where $\pi$ and $\bar\pi$ are conjugate primes in $\mathbf{Z}[\varphi]$ that do not differ by a unit. Write $\pi=x+y\varphi$, so $x+y\varphi\equiv 0\pmod{\pi}$. Now, if $p|y$, then $\pi|y,x$, contradiction, so $p\nmid y$. Thus, $y$ has an inverse modulo $p$, say $y'$. Then we have $\pi|p|yy'-1$, so $\varphi\equiv -xy'\pmod{\pi}$. Summarizing, $\varphi\equiv k\pmod{\pi}$ for some integer $k\not\equiv 0\pmod{p}$. By FLT, $k^{p-1}\equiv 1\pmod{p}$, so $\varphi^{p-1}\equiv k^{p-1}\pmod{\pi}$. Thus $\varphi^{p-1}\equiv 1\pmod{\pi}$. Similarly, we see that $\bar\varphi^{p-1}\equiv 1\pmod{\pi}$, so $F_{p-1}\sqrt{5}\equiv 0\pmod{\pi}$. Since $p$ and $5$ are necessarily relatively prime, $\pi|F_{p-1}$, and $\bar\pi|F_{p-1}$. Hence $\pi\bar\pi = p|F_{p-1}$ in this case.

Now, suppose $\left(\frac{5}{p}\right)=-1$. We have $5^{(p-1)/2}\equiv -1\pmod{p}$, by Euler's Criterion. Now, applying the Binomial-theorem to Binet's formula yields several terms containing $\binom{p+1}{k}\equiv 0\pmod{p}$. After reducing modulo $p$ we will be left with $\dfrac{\sqrt{5}^{p+1}+1}{2^t}$ for some $t$, which is also divisible by $p$ (by working in $\mathbf{Z}[\varphi]$), so $p|F_{p+1}$ in this case.

Note: This is a proof of the above post by 01000100, which asserts that $p|F_{p-\left(\frac{p}{5}\right)}$

-

The trivial answer is: yes $F_0=0$ is a multiple of any prime (or indeed natural) number. But this can be extended to answer your real question: does this also happen (for given$~p$) for some $F_n$ with $n>0$.

Indeed, the first coefficient (the one of $F_{n-2}$, which is $1$) of the Fibonacci recurrence is obviously invertible modulo any prime$~p$, which means the recurrence can be run backwards modulo$~p$: knowing the classes of $F_{n-1}$ and of $F_n$ one can recover the class of$~F_{n-2}$ uniquely. This means that on the set $\Bbb F_p^2$ of pairs of classes of successive terms, the Fibonacci recurrence defines a bijection (a permutation of all pairs). Then since the set of pairs is finite, some power of this operation must be the identity on it. This implies that the case $F_n\equiv0\pmod p$ that happens for $n=0$ recurs for some $n>0$.

-

Any linearly recursive integer sequence has the property that every large enough prime divides some term, as long as

some term of the sequence is equal to $0$.

That follows from the solution of linear recursive sequences. Number the sequence so that $S_0 = 0$, and consider primes $p$ not dividing any of the denominators or characteristic roots that appear in the algebraic solution of the recurrence (this is all but a finite number of primes). If $k$ is chosen so that $\alpha^k=1 \mod p$ for all roots $\alpha$ of the characteristic polynomial, then $p|S_k$ if the roots are distinct, and $p|S_{kp}$ whether or not the roots are distinct.

If the sequence has the additional property that

the recursion can be run backward (its extreme coefficients are $\pm 1$)

then every prime divides some term of the sequence.

The second statement is what was proved in the other answers: when reduced mod $p$, a recursion that can be run in both directions is periodic and thus repeats the value of $0$.

The converse, that there must exist a term equal to $0$ in order to have a term equal to $0$ mod $p$ for all large $p$, is plausible but seems difficult to prove.

-