Prove that $F_{125n}$ is divisible by $125$.

Question

$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!

Answer 1

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$$

Answer 2

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

Answer 3

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

Answer 4

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.