I haven't written in way too long and just wanted to post this fun little proof.
Assertion: Let \(F_n\) be the \(n\)th Fibonacci number defined by \(F_n = F_{n-1} + F_{n-2}\), \(F_0 = 0, F_1 = 1\). Show that for an odd prime \(p\neq 5\), we have \(p\) divides \(F_{p^2−1}\).
Proof: We do this by working inside \(\mathbb{F}_p\) instead of working in \(\mathbb{R}\). The recurrence is given by
\[ \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)
\left( \begin{array}{c}
F_{n-1} \\
F_{n-2} \end{array} \right)
=
\left( \begin{array}{c}
F_{n-1} + F_{n-2} \\
F_{n-1} \end{array} \right)
=
\left( \begin{array}{c}
F_n \\
F_{n-1} \end{array} \right)\]
and in general
\[ \left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{n}
\left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
\left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{n}
\left( \begin{array}{c}
F_1 \\
F_0 \end{array} \right)
=
\left( \begin{array}{c}
F_{n + 1} \\
F_n \end{array} \right)\]
The matrix \(A = \left(\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right)\) has characteristic polynomial
\[\chi_A(t) = (1 - t)(0 - t) - (1)(1) = t^2 - t - 1\]
If this polynomial has distinct roots, then \(A\) is diagonalizable (this is sufficient, but not necessary). Assuming the converse we have \(\chi_A(t) = (t - \alpha)^2\) for some \(\alpha \in \mathbb{F}_p\); we can assume \(\alpha \in \mathbb{F}_p\) since \(-2\alpha = -1\) is the coefficient of \(t\), which means \(\alpha = 2^{-1} \) (we are fine with this since \(p\) odd means that \(2^{-1}\) exists). In order for this to be a root of \(\chi_A\), we must have
\[0 \equiv 4 \cdot \chi_A\left(2^{-1}\right) \equiv 4 \cdot \left(2^{-2} - 2^{-1} - 1\right) \equiv 1 - 2 - 4 \equiv -5 \bmod{p}.\]
Since \(p \neq 5\) is prime, this is not possible, hence we reached a contradiction and \(\chi_A\) does not have a repeated root.
Thus we may write \(\chi_A(t) = (t - \alpha)(t - \beta)\) for \(\alpha, \beta \in \mathbb{F}_{p^2}\) (it's possible that \(\chi_A\) is irreducible over \(\mathbb{F}_p\), but due to degree considerations it must split completely over \(\mathbb{F}_{p^2}\)). Using this, we may write
\[A = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right) P^{-1}\]
for some \(P \in GL_{2} \left(\mathbb{F}_{p^2}\right)\) and so
\[A^{p^2 - 1} = P \left(\begin{array}{cc} \alpha & 0 \\ 0 & \beta \end{array} \right)^{p^2 - 1} P^{-1}
= P \left(\begin{array}{cc} \alpha^{p^2 - 1} & 0 \\ 0 & \beta^{p^2 - 1} \end{array} \right)P^{-1}\]
Since \(\chi_A(0) = 0 - 0 - 1 \neq 0\) we know \(\alpha\) and \(\beta\) are nonzero, hence \(\alpha^{p^2 - 1} = \beta^{p^2 - 1} = 1 \in \mathbb{F}_{p^2} \). Thus \(A^{p^2 - 1} = P I_2 P^{-1} = I_2\) and so
\[\left( \begin{array}{c}
F_p \\
F_{p^2 - 1} \end{array} \right)
=
\left( \begin{array}{cc}
1 & 1 \\
1 & 0 \end{array} \right)^{p^2 - 1}
\left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
I_2 \left( \begin{array}{c}
1 \\
0 \end{array} \right)
=
\left( \begin{array}{c}
1 \\
0 \end{array} \right)\]
so we have \(F_{p^2 - 1} = 0\) in \(\mathbb{F}_p\) as desired.
