Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

Show that if n divides a single Fibonacci number, then it will divide infinitely many Fibonacci numbers.

share|improve this question

marked as duplicate by Steven Stadnicki, user127096, mookid, Mario Carneiro, Paul Apr 8 at 1:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
Actually, you can do better: Any $n$ divides infinitely many Fibonacci numbers. –  Phira Apr 7 at 23:12
    
Prove by contradiction that Fibonacci number $N$ is not the largest Fibonacci number that is divisible by $n$ by construction. –  Sudarsan Apr 7 at 23:14
    
@Phira What is the relevant result for this claim? –  Mario Carneiro Apr 7 at 23:17
3  
@MarioCarneiro $(F_k,F_{k+1}) \mod n$ has to repeat eventually. Since it starts out with $F_0=0$, you get 0 again and again. –  Phira Apr 7 at 23:18

6 Answers 6

Actually every nonzero integer $m$ divides infinitely many Fibonacci numbers.

Consider the Fibonacci sequence modulo $m$. It still satisfies the recurrence $F_n\equiv F_{n-1}+F_{n-2}\pmod m$, and since there are only finitely many possible pairs $(F_{n-1},F_{n-2})$ it will repeat sooner or later.

Because we also have $F_{n-2} \equiv F_n - F_{n-1} \pmod m$ we can run the recurrence backwards, so the repeating part of the sequence starts out right from $F_0$.

Since $F_0=0$, there will be at least one $F_i\equiv 0\pmod m$ for each period of the repetition -- that is, infinitely many times.

share|improve this answer
    
Essentially the same as Phira's comment, but good nonetheless. +1 –  Mario Carneiro Apr 7 at 23:33
    
Is this period known in any closed form? –  Mario Carneiro Apr 7 at 23:35
1  
@MarioCarneiro: Yes, I saw Phira's comment, but it deserved to appear as an answer too. The periods are A001175 in OEIS; there doesn't seem to be a nice closed formula known for them. –  Henning Makholm Apr 8 at 0:35

From Wikipedia:

$$\gcd(F_m,F_n)=F_{\gcd(m,n)}$$

Thus if $m\mid n$, $\gcd(m,n)=m$ so $\gcd(F_m,F_n)=F_m$ and $F_m\mid F_n$.

Therefore if $d\mid F_n$, $d\mid F_{kn}$ for all $k\in\Bbb N$.

share|improve this answer

You can prove by induction that $F_{km}\equiv0\pmod{F_k}$ for all $m\ge1$.

share|improve this answer

Hint $\,\ {\rm mod}\ n\!:\,$ the shift map $\ (f_i,f_{i-1})\mapsto (f_{i+1},f_i)$ is an invertible map $\,(a,b)\mapsto (a\!+\!b,a)\,$ on a finite set, so a permutation. Thus its orbits are cycles (i.e. have no preperiodic part). Hence if $\,f_k\equiv 0\,$ then $\,(0,f_{k-1})\,$ occurs in the orbit of $\,(f_1,f_0)$ so this value is taken by infinitely many $\,(f_j,f_{j-1}),\,$ every time the map cycles back to the same place in the finite cycle.

Remark $\ $ Such cyclical structure of permutation orbits is often reinvented from scratch in concrete instances like this - which I refer to as reinventing the wheel (cycle). One can find many examples in my prior posts (including competition problems). Here's a typical example:

> A sequence f(n) satisfies the relation f(n+2) = [f(n+1)]^2 - f(n), 
> with f(1) = 39 and f(2) = 45.  Prove that 1986 divides infinitely 
> many terms of the sequence. 

Since the recursion determines unique values $\rm\:f_{n+2},\:f_n\:$ when run fore/backward, the shift map on the sequence induces a permutation $\rm\:F\:$ on integer pairs $$\rm mod\ \ 1986\!:\ \ F(f_n,f_{n+1})\ =\ (f_{n+1},f_{n+2})\quad i.e.\quad F(a,b)\: =\ (b,b^2-a)\ \ $$ But $\,0\,$ occurs in the cycle containing $\,(39,45)\,$ since $\rm\:F(39,45) = (45,0),\,$ so $\,0\,$ occurs infinitely often in this finite cycle when $\rm\,F\,$ is iterated.

share|improve this answer
3  
If you don't mind my asking, why do you always use such peculiar spacing conventions and use upright text for your variables? Is there a specific style you are aiming for? –  Mario Carneiro Apr 7 at 23:47
2  
@Mario That part is excerpted from a very old answer, back when MathJax typeset italic text horribly (so my macros used roman fonts as a workaround), and had spacing problems galore. –  Bill Dubuque Apr 7 at 23:49

Let $S$ be the shift operator on indices. Then the recursion for the Fibonacci Sequence is $$ 0=(S^2-S-1)F_n=(S-\phi)(S-(-1/\phi))F_n\tag{1} $$ Since $x-a\mid x^k-a^k$, we also get $$ 0=\left(S^k-\phi^k\right)\left(S^k-(-1/\phi)^k\right)F_n=\left(S^2-\left(\phi^k+(-1/\phi)^k\right)S+(-1)^k\right)\tag{2} $$ The Lucas Numbers, $L_k$, which satisfy the same defining recursion as the Fibonacci numbers, are given by $$ L_k=\phi^k+(-1/\phi)^k\tag{3} $$ Thus, combining $(2)$ and $(3)$, we have $$ F_{n+2k}=L_kF_{n+k}+(-1)^{k-1}F_n\tag{4} $$ If we set $n=mk$, we get $$ F_{(m+2)k}=L_kF_{(m+1)k}+(-1)^{k-1}F_{mk}\tag{5} $$ Thus, for any $k$, we have a recursion on the $k^{th}$ Fibonacci Numbers. Since $F_0=0$, recursion $(5)$ guarantees that $F_{mk}$ is divisible by $F_k$.

share|improve this answer

Hint: You can show by induction that for any fixed $N$, $$F_{N+k} = F_{k-1}F_{N+1}+F_{k-2}F_{N}$$ Thus if $n$ divides $F_{N}$, it'll also divide $F_{2N+1}$.

share|improve this answer
    
Are you numbering so that $F_0=0$? If so, then if $m\mid n$ then $F_m\mid F_n$. –  robjohn Apr 7 at 23:24
    
This seems fishy, since I can plainly see that, for example, $F_3\nmid F_7$. –  Mario Carneiro Apr 7 at 23:25
    
@MarioCarneiro: this assumption is that $n$ "divides a single Fibonacci number". I chose this Fibonacci number to be named $F_N$. (robjohn: I took $F_0=1$, but otherwise shifting the index will do the trick) –  Clement C. Apr 7 at 23:26
    
@MarioCarneiro: thanks for pointing this out -- I meant to write $n|F_N$, not $N|F_N$. –  Clement C. Apr 7 at 23:28

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