3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – David Quinn Mar 23 '18 at 20:47
  • 1
    $\begingroup$ As shown here we actually have something stronger, namely $$ \nu_5(F_k) = \nu_5(k).$$ $\endgroup$ – Jack D'Aurizio Mar 23 '18 at 20:52
  • $\begingroup$ @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. $\endgroup$ – Michael Rozenberg Mar 23 '18 at 20:53
  • $\begingroup$ So you should change your question text to "can we..." rather than "we can..." and add a question mark $\endgroup$ – David Quinn Mar 23 '18 at 21:00
  • $\begingroup$ @David Quinn My English is very bad. Can you fix my question such that it should be seen right? $\endgroup$ – Michael Rozenberg Mar 23 '18 at 21:13
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Malcolm Mar 23 '18 at 23:30
  • $\begingroup$ @Malcolm Whether there are any primes $p$ with $D(p^2) = D(p)$ is an unsolved problem. $\endgroup$ – Slade Mar 24 '18 at 9:06
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Slade Mar 24 '18 at 9:09
  • $\begingroup$ @Slade Thank-you very much, you confirm what I vaguely recalled. $\endgroup$ – Malcolm Mar 24 '18 at 11:32
  • $\begingroup$ @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. $\endgroup$ – DanielWainfleet Mar 25 '18 at 5:48
0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.