Fibonacci recurrence matrix modulo an integer ($A=\left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)$)

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(\mathrm{mod}2)$, $A^8\equiv I(\mathrm{mod}3)$, and $A^5\equiv 3I(\mathrm{mod}5)$. The last congruence gives $F_{n+5}\equiv 3F_n(\mathrm{mod}5)$, hence $5\mid F_{5j}$ for every nonnegative $j$.