Does every prime divide some Fibonacci number?

I am tring to show that aPnN:a|Fn, where F is the fibonacci sequence defined as {Fn}:F0=0,F1=1,Fn=Fn1+Fn2 (n=2,3,...). How can I do this?

Originally, I was trying to show that aNnN:a|Fn. 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.

Answer

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

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

That is, you have F0=0, F1=1, and for n0, 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 pth Pisano period; of course some smaller n may also exist (for which F’_{n+1} \not\equiv 1 \mod p).

Attribution
Source : Link , Question Author : Chanhee Jeong , Answer Author : ShreevatsaR

Leave a Comment