Fibonacci Mystery I saw this on a "numberphile" video and tried to prove it but couldn't do anything.
Theorem: Let $n \ge 2$ and $F_m$ is the $m^{\text{th}}$ number in the Fibonacci sequence. Then, if we look all $F_m$ ($m \ge 1$)  in modulo $n$, we will have a cycle. This cycle can only contain $1$ zero, $2$ zero or $4$ zero.
Thanks for any help.
 A: For the first part: There are only finitely many possible choices for 
$$(F_{m-1},F_m) \pmod{n} \,.$$ 
Thus, there exists some $m < k$ so that
$$(F_{m-1},F_m) \pmod{n} = (F_{k-1},F_k) \pmod{n} \,.$$
Now, prove by induction that 
$$F_{l} \equiv F_{l+k-m} \pmod n$$
Alternate solution If you know matrices, there is a simpler solution.
You know that
$$\begin{pmatrix} 
F_{m+1} & F_m \\
F_{m} & F_{m-1} \end{pmatrix}= \begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^m$$
Now, by Lagrange Theorem,
$$\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^k \equiv I_2 \pmod{n}$$
where $k$ is the order of $GL_2(\mathbb Z/m\mathbb Z)$. Thus
$$\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{m+k} \equiv \begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^m \pmod{n}$$
For the second part: As mark pointed, if $F_k \equiv 0 \pmod{n}$ then $F_{k-1}=F_{k+1}= r \pmod n$ for some $r$. Then
$$\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^k= \begin{pmatrix} 
F_{k+1} & F_k \\
F_{k} & F_{k-1} \end{pmatrix}= r I_2 \pmod n$$
thus, by taking determinants, we get $r^2 \equiv \pm 1 \pmod n$ and hence
$$\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{2k}=  r^2 I_2= \pm I_2\pmod n$$
and hence
$$\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{4k}= I_2\pmod n$$
thus, if $F_k \equiv 0 \pmod n$ then $4k$ is a period for $F_m \pmod n$, and from here the conclusion follows immediately (note also that $\begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{2k}, \begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{3k}, \begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^{4k}$ are all three diagonal matrices, thus have a zero inside).
P.S.(added) The reason why we get $1,2$ or $4$ is simple: if $k$ is the smallest positive integer for which $F_k \equiv 0 \pmod n$, then we showed that
$$ \begin{pmatrix} 
1 & 1 \\
1 & 0 \end{pmatrix}^k= r I_2 \pmod n$$
and $r^4 \equiv 1 \pmod n$. It is easy to show that the number of zeroes is exactly the order of $r \pmod n$.
