# 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}$.

• – lab bhattacharjee Jun 15 '16 at 11:48
• Is $$(2,5^k)=5^k$$ for $k\ge1$? – lab bhattacharjee Jun 15 '16 at 11:57
• In fact, $F_{5^n} \equiv 5^n \bmod 10^n$ and it seems that $5^n$ is the largest power of $5$ that divides $F_{5^n}$. – lhf Jun 16 '16 at 14:28

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}$.
• Now that we have aids like WA, we can dare compute $A^5$ just to see what comes out... – lhf Jun 15 '16 at 15:00
• $5$ seems to be very special here: there is no obvious multiple of $k$ in $c$ for $k\ne 5$. – lhf Jun 16 '16 at 14:21