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

-
Are you missing a detail here? Are you saying that this holds for any choice of $n$, i.e. modulo any integer? –  Fly by Night Sep 20 '13 at 18:57
@FlybyNight It claims that $n\ge2$, but that's it... (So not exactly any choice of $n$) –  apnorton Sep 20 '13 at 18:59
It's for any choice of n. –  Konformist Liberal Sep 20 '13 at 18:59
@Tobias: Cycle here surely means that Fibonacci sequence becomes periodic (a well known fact). –  Jyrki Lahtonen Sep 20 '13 at 19:01
Note that when we reach zero, the sequence goes $\dots r, 0, r, r \dots$ so the repeat sequence (mod $n$) is $r$ times the original sequence. It is also known that $F_r|F_{kr}$ for positive integers $k$. –  Mark Bennet Sep 20 '13 at 19:21

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

-
You can also prove quickly that there exists at least one $0$ in the period: for $n>1$ the modded cycle always begins $1,1$, hence the cycle must end with a $0$ to get the recursion correct. –  A Walker Sep 20 '13 at 19:08
It seems like the real meat of this question is how to show the cycle has 1,2, or 4 zeros mod $n$. –  user2566092 Sep 20 '13 at 19:10
@AWalker But how do you know that the $(1,1)$ pattern will recur? In general, even if there is a cycle, it could start with a sequence not part of the cycle. –  Harald Hanche-Olsen Sep 20 '13 at 19:11
@HaraldHanche-Olsen That follows immediately from the Matrix proof. If $k$ is as in the proof we have $$\begin{pmatrix} F_{k+1} & F_k \\ F_{k} & F_{k-1} \end{pmatrix}= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k=\begin{pmatrix} 1 & 0 \\ 0& 1 \end{pmatrix}$$ Thus $F_{k+1}=1, F_k=0 \pmod{n}$. Now what is $F_{k+2}$? –  N. S. Sep 20 '13 at 19:19
@Harald: The recurrence will work backwards as well as forwards. Thus the sequence is periodic, not just eventually periodic. –  Jyrki Lahtonen Sep 20 '13 at 19:21