<s>[INST] Fibonacci numbers divisible by p for some prime p? This came up in a series of notes on number theory I'm reading. The question is:
Prove that the $(p-1)$th or the $(p+1)$th Fibonacci number is divisible by $p$ for some prime $p$ 
I'm very much lost on this question, so I thought I'd see if I could find a proof here.
 [/INST] Fix a prime $p\ge 7$. We have by Cassini's identity that
$$
F_{p-1}F_{p+1} = F_p^2-(-1)^{p-1} \,\,\,\,(=\, F_p^2-1).
$$
Hence, it is enough to prove that
$$
F_p^2 \equiv 1\pmod{p}.
$$
But we have
\begin{align*}
F_p^2&=\left(\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^p-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^p\right)^2 \\\
&=\frac{1}{5}\left(\frac{1+\sqrt{5}}{2}\right)^{2p}+\frac{1}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{2p}-\frac{2}{5}(-1)^p \\\
&=\frac{1}{5\cdot 2^{2p}}\left(1+\sqrt{5}\right)^{2p}+\frac{1}{5\cdot 2^{2p}}\left(1-\sqrt{5}\right)^{2p}+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p}}\left(3+\sqrt{5}\right)^{p}+\frac{1}{5\cdot 2^{2p}}\left(3-\sqrt{5}\right)^{2p}+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p}}\left(2\sum_{i=0, i\text{ even}}^p\binom{p}{i}3^{p-i}\sqrt{5}^i\right)+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p-1}}\left(\sum_{j=0}^{\frac{p-1}{2}}\binom{p}{2j}3^{p-2j}5^j\right)+\frac{2}{5}.
\end{align*}
At this point, considering that $p\mid \binom{p}{j}$ for $0<j<p$, we conclude that
$$
F_p^2 \equiv \frac{3^p}{5\cdot 2^{p-1}}+\frac{2}{5}\equiv \frac{3}{5}+\frac{2}{5}\equiv 1\pmod{p}.
$$
</s>