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.

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