Show that if n divides a single Fibonacci number., then it will divide infinitely many Fibonacci numbers. Show that if n divides a single Fibonacci number, then it will divide infinitely many Fibonacci numbers.
 A: 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$.
A: 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.
A: 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.
A: You can prove by induction that $F_{km}\equiv0\pmod{F_k}$ for all $m\ge1$.
A: 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$.
A: 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}$.
