= Solution
The same recurrence <matrix> has
$$
A^5=A^3A^2=\begin{pmatrix}8&5\\5&3\end{pmatrix}\equiv3I\pmod5.
$$
Therefore $\mathbf v_{n+5}\equiv3\mathbf v_n\pmod5$, and in particular $F_{n+5}\equiv3F_n\pmod5$. Starting from $F_0=0$ and iterating,
$$
F_{5j}\equiv3^jF_0=0\pmod5.
$$
Consequently \b[every nonnegative index divisible by five has a Fibonacci number divisible by five], including index zero. This directly proves the requested divisibility without assuming a general Fibonacci divisibility theorem.
Back to article page
