1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you missing a detail here? Are you saying that this holds for any choice of $n$, i.e. modulo any integer? $\endgroup$ – Fly by Night Sep 20 '13 at 18:57
  • $\begingroup$ @FlybyNight It claims that $n\ge2$, but that's it... (So not exactly any choice of $n$) $\endgroup$ – apnorton Sep 20 '13 at 18:59
  • $\begingroup$ It's for any choice of n. $\endgroup$ – Konformist Liberal Sep 20 '13 at 18:59
  • 1
    $\begingroup$ @Tobias: Cycle here surely means that Fibonacci sequence becomes periodic (a well known fact). $\endgroup$ – Jyrki Lahtonen Sep 20 '13 at 19:01
  • 2
    $\begingroup$ 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$. $\endgroup$ – Mark Bennet Sep 20 '13 at 19:21
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – awwalker Sep 20 '13 at 19:08
  • 1
    $\begingroup$ It seems like the real meat of this question is how to show the cycle has 1,2, or 4 zeros mod $n$. $\endgroup$ – user2566092 Sep 20 '13 at 19:10
  • $\begingroup$ @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. $\endgroup$ – Harald Hanche-Olsen Sep 20 '13 at 19:11
  • $\begingroup$ @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}$? $\endgroup$ – N. S. Sep 20 '13 at 19:19
  • $\begingroup$ @Harald: The recurrence will work backwards as well as forwards. Thus the sequence is periodic, not just eventually periodic. $\endgroup$ – Jyrki Lahtonen Sep 20 '13 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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