<s>[INST] Show that $5^n$ divides $F_{5^n}$. If $F_n$ denotes the $n$-th Fibonacci number ($F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n$), show that $5^n$ divides $F_{5^n}$.
 [/INST] Note that
$$
\begin{pmatrix}a+b & a \\ a & b\end{pmatrix}^5
=
\begin{pmatrix}* & c \\ c & *\end{pmatrix}
$$
where $c=5 a (a^4 + 3 a^3 b + 4 a^2 b^2 + 2 a b^3 + b^4)$. Therefore, if $5^n$ divides $a$, then $5^{n+1}$ divides $c$.
Apply this to
$$
\begin{pmatrix}1&1\\1&0\end{pmatrix}^n
=
\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}
$$
for a proof by induction that $5^n$ divides $F_{5^n}$.
</s>