Divisibility of Fibonacci numbers This question is inspired by a Project Euler problem I was working on.  Noticing something that did not make sense led me to the conclusion that for all primes $p$ ending in $1$ or $9$, the $(p-1)$st Fibonacci number is divisible by $p$.  I haven't proven it, but it's the only conclusion that makes sense.  I'd give more information on how I arrived there but I'm afraid it might spoil the problem.
I have tested this for the first few values using an online Fibonacci calculator
$$F_{10}=55=5\times11$$
$$F_{18}=2584=136\times19$$
$$F_{28}=317811=10959\times29$$
$$F_{30}=832040=26840\times31$$
Why is this true, assuming it's true at all?
 A: It's true because $5$ is a quadratic residue modulo an odd prime $p \neq 5$ if and only if $p \equiv \pm 1 \pmod{5}$. The relevance of $5$ can be seen from Binet's formula
$$F_n = \frac{\varphi^n - \psi^n}{\varphi - \psi},$$
where
$$\varphi = \frac{1+\sqrt{5}}{2};\quad \psi = \frac{1-\sqrt{5}}{2} = 1 - \varphi = -\frac{1}{\varphi}.$$
Using $\varphi - \psi = \sqrt{5}$, we can expand
$$\begin{align}
2^{p-1}F_p &= \frac1{2\sqrt{5}} \left(\sum_{k=0}^p \binom{p}{k}\sqrt{5}^k - \sum_{k=0}^p \binom{p}{k}(-\sqrt{5})^k\right)\\
&= \sum_{k=0}^{\frac{p-1}{2}} \binom{p}{2k+1}5^k\\
&\equiv 5^{\frac{p-1}{2}} \pmod{p}.
\end{align}$$
Now $2^{p-1}\equiv 1 \pmod{p}$, and $5^{\frac{p-1}{2}} \equiv \left(\frac{5}{p}\right)\pmod{p}$, where $\left(\frac{a}{p}\right)$ is the Legendre symbol, that is $\left(\frac{a}{p}\right) = 1$ if $a$ is a quadratic residue modulo $p$, $= -1$ if $a$ is a quadratic non-residue modulo $p$.
A similar computation shows that
$$F_{p+1} \equiv \frac{1 + \left(\frac{5}{p}\right)}{2} \pmod{p}.$$
So if $\left(\frac5p\right) = -1$, that is, if $p \equiv \pm 2 \pmod 5$, then $F_{p+1}$ is a multiple of $p$, and if $\left(\frac5p\right) = 1$, that is, $p \equiv \pm 1 \pmod 5$, then $F_p \equiv F_{p+1} \equiv 1 \pmod{p}$, and hence 
$$F_{p-1} = F_{p+1} - F_p \equiv 0 \pmod{p}.$$
A: By quadratic reciprocity, $x^2=5$ has a solution in $\mathbb F_p$ iff $y^2=p$ has a solution in $\mathbb F_5$, i.e. iff $p=5n\pm 1$. In that case we can substitute the solution of $x^2=5$ to $F_n=\frac{1}{\sqrt{5}}(a^n-b^n)$, where $a=(1+\sqrt{5})/2$, $b=(1-\sqrt{5})/2$. Since $c^{p-1}=1$ for every $c\in\mathbb F_p$, $c\neq 0$, we get that $F_{p-1}=0$ in $\mathbb F_p$.
