Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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$) –  anorton Sep 20 '13 at 18:59
    
It's for any choice of n. –  Konformist Liberal Sep 20 '13 at 18:59
1  
@Tobias: Cycle here surely means that Fibonacci sequence becomes periodic (a well known fact). –  Jyrki Lahtonen Sep 20 '13 at 19:01
2  
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

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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