Fibonacci recurrence matrix modulo an integer
= Fibonacci recurrence matrix modulo an integer
{c}
{title2=$A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$}
The vector $(F_{n+1},F_n)^T$ advances by multiplication by $A$. Matrix powers therefore prove modular recurrence identities uniformly in $n$. Explicitly, $A^3\equiv I\pmod2$, $A^8\equiv I\pmod3$, and $A^5\equiv3I\pmod5$. The last congruence gives $F_{n+5}\equiv3F_n\pmod5$, hence $5\mid F_{5j}$ for every nonnegative $j$.