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.
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$).
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.
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.
