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

• Does it not follow directly from what you have already? Put $n=5p$ where $p\in\mathbb{Z}_+$ and then you have an expression divisible by $25$ then repeat with $p=5q$ likewise... – David Quinn Mar 23 '18 at 20:47
• As shown here we actually have something stronger, namely $$\nu_5(F_k) = \nu_5(k).$$ – Jack D'Aurizio Mar 23 '18 at 20:52
• @David Quinn Easy to see that $F_{25n}$ is divisible by $25$ and from here $F_{125n}$ is divisible by $125$. But we need to prove the above formula. – Michael Rozenberg Mar 23 '18 at 20:53
• So you should change your question text to "can we..." rather than "we can..." and add a question mark – David Quinn Mar 23 '18 at 21:00
• @David Quinn My English is very bad. Can you fix my question such that it should be seen right? – Michael Rozenberg Mar 23 '18 at 21:13

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

• – lhf Mar 26 '18 at 13:56

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

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

• I'm interested in your BTW. I assume you are extending your definition of $D$ so that $D(k)$ is the least $n\in\Bbb N$ such that $k|F_n$. Do you have a reference that $D(p^2)$ is never equal $D(p)$? Thanks. – Malcolm Mar 23 '18 at 23:30
• @Malcolm Whether there are any primes $p$ with $D(p^2) = D(p)$ is an unsolved problem. – Slade Mar 24 '18 at 9:06
• The BTW requires additional assumptions. It should be something like: $D(p^m) = p^{m-n} D(p^n) = p^{m-n} D(p)$, where $n$ is the largest integer with $D(p^n) = D(p)$. – Slade Mar 24 '18 at 9:09
• @Slade Thank-you very much, you confirm what I vaguely recalled. – Malcolm Mar 24 '18 at 11:32
• @Slade. Yes. My BTW has an error. What I should have said was that if $p$ is an odd prime and $F_{D(p)}$ is divisible by $p^k$ then $D(p^{k+n})=p^nD(p).$... It is an unsolved conjecture that $p^2$ does not divide $F_{D(p)}$ for every prime $p.$ Thanks for the comment. – DanielWainfleet Mar 25 '18 at 5:48

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.

• How does this result help solve the problem? Are you trying to prove that $F_m\mid F_n$ when $m\mid n$? – Batominovski Jul 29 '18 at 12:44