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

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

-

## marked as duplicate by Steven Stadnicki, user127096, mookid, Mario Carneiro, PaulApr 8 '14 at 1:46

Actually, you can do better: Any $n$ divides infinitely many Fibonacci numbers. –  Phira Apr 7 '14 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 '14 at 23:14
@Phira What is the relevant result for this claim? –  Mario Carneiro Apr 7 '14 at 23:17
@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 '14 at 23:18

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.

-
Essentially the same as Phira's comment, but good nonetheless. +1 –  Mario Carneiro Apr 7 '14 at 23:33
Is this period known in any closed form? –  Mario Carneiro Apr 7 '14 at 23:35
@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 '14 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$.

-

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

-

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.

-
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 '14 at 23:47
@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 '14 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$.

-

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

-
Are you numbering so that $F_0=0$? If so, then if $m\mid n$ then $F_m\mid F_n$. –  robjohn Apr 7 '14 at 23:24
This seems fishy, since I can plainly see that, for example, $F_3\nmid F_7$. –  Mario Carneiro Apr 7 '14 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 '14 at 23:26
@MarioCarneiro: thanks for pointing this out -- I meant to write $n|F_N$, not $N|F_N$. –  Clement C. Apr 7 '14 at 23:28