Prove that $F_{125n}$ is divisible by $125$. 
$F_{n+2}=F_{n+1}+F_n$, $F_1=F_2=1$.
Prove that $F_{125n}$ is divisible by $125$.

How we can prove it by easiest way?
For example, I know that we can prove that:
$$F_{5n}=25F_n^5+25(-1)^nF_n^3+5F_n.$$
Because from here it follows, although I think it's very ugly.
Thank you!
 A: My favorite Fibonacci technique is
the matrix formulation, which is well worth knowing and easily proved:
$$
A^n=
\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=
\begin{pmatrix}F_{n+1}&F_n\\F_n&F_{n-1}\end{pmatrix}
$$
Now, $A^2=A+I$ and so $A^5=5A+3I$. Then
$$
A^{25}=(5A+3I)^5=(5A)^5+ 5 (5A)^4 (3I) + 10 (5A)^3 (3I)^2 + 10 (5A)^2 (3I)^3 + 5 (5A) (3I)^4 + (3I)^5
= 25B + 3^5 I  
$$
and then $A^{125}=(25B + 3^5 I)^5 = 125C + 3^{25} I$.
Therefore, all powers of $A^{125}$ are diagonal mod $125$ and so $F_{125n} \equiv 0 \bmod 125$.
A: It is enough to prove that $125\mid F_{125}$ since for each $a\mid b$ we have $F_a\mid F_b$.
We use $$ F_{2n} = (2F_{n-1}+F_{n})F_{n}$$ and $$F_{2n-1} = F_{n}^2+F_{n-1}^2$$
All the congruences are modulo $125$. 
$$ F_{14} = 377 \equiv  2$$
$$ F_{15} = 610 \equiv -15$$
$$ F_{16} = 987 \equiv -13$$
$$F_{30} = (2F_{14}+F_{15})F_{15} \equiv (4-15)(-15) \equiv 40 $$
$$F_{31} = F_{16}^2+F_{15}^2 \equiv 169+225 \equiv 44-25 = 19 $$
$$F_{32} = (2F_{15}+F_{16})F_{16} \equiv (30+13)13 \equiv  59 $$
$$F_{62} = (2F_{30}+F_{31})F_{31} \equiv (80+19)19 \equiv 6  $$
$$F_{63} = F_{32}^2+F_{31}^2  \equiv -19-14 \equiv -33$$
$$F_{125} = F_{63}^2+F_{62}^2= 36+1089 = 1125  \equiv 0$$
A: Let $M$ be the $2\times 2$ matrix with top row $(1,1)$ and bottom row $(1,0).$
By induction on $n,$ the top row of $M^n$ is $(F_{n+1},F_n)$ and the bottom row is $(F_n, F_{n-1}).$
By comparing the entries of $M^{mn}$ with those of $M^m\cdot M^{m(n-1)}$ we see that $F_m$ divides $F_{mn}.$
So it suffices to show that $125|F_{125}$ which has already been done in the A from ChristianF.
BTW....More generally, every prime $p$ is a divisor of some positive $F_n.$ Let $D(p)$ be the least $n\in \Bbb N$ such that $p|F_n.$ If $p$ is an  $odd$  prime and $m>1$ then $D(p^m)=p^{m-1}D(p).$ So $D(5^3)=5^2D(5)=5^3.$
A: At first we prove 
$a_{n+m}\equiv 0  \pmod {a_m} \Leftrightarrow a_n\equiv0 \pmod {a_m}\tag 1$. 
lemma 1  $a_{n+m}=a_{n-1}a_m+a_na_{m+1}$
$\Rightarrow a_{n+m}=a_na_{m+1} \pmod {a_m}$
$(1)$ was proved. Then when put $F_0=0$, the statement become obvious.
