1

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.

aeyalcinoglu
  • 534
  • 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. – aeyalcinoglu Sep 20 '13 at 18:59
  • The existence of a cycle is easy, because there are at most $n^2$ possibities for two consecutive numbers modulo $n$. – Harald Hanche-Olsen Sep 20 '13 at 19:00
  • What does a cycle mean in this context? – Tobias Kildetoft Sep 20 '13 at 19:00
  • 1
    @Tobias: Cycle here surely means that Fibonacci sequence becomes periodic (a well known fact). – Jyrki Lahtonen Sep 20 '13 at 19:01
  • @Tobias It can only mean there is some $k$ so that $F_{k+j}\equiv F_j\bmod n$ for all $j$ sufficiently large. – Harald Hanche-Olsen Sep 20 '13 at 19:01
  • @anorton I had taken the OP's assumption to be tacit. – Fly by Night Sep 20 '13 at 19:04
  • The case when the modulus is a prime other than $2$ or $5$ (that can be just checked manually) is relatively straight forward. It follows from Binet's formula that we get a zero residue only once per period or every half period depending on the order of the Golden ratio in the field $\mathbb{F}_{p^2}$. I'm not ruling out the possibility that an open bottle of Lagavullin impairs my thinking though. With $n=5$ we seem to have four zeros in a period. – Jyrki Lahtonen Sep 20 '13 at 19:12
  • 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
  • @JyrkiLahtonen $p = 113$ has four zeros in the period. We have a zero when $\varphi^{2n} \equiv (-1)^n \pmod{p}$, so that leaves $1,2,4$ as possibilities. – Daniel Fischer Sep 20 '13 at 19:25
  • @Daniel: At least we are counting it the same way! For some reason I thought that the order of $-\phi^2$ is either the period or half the period, because the period is the l.c.m. of orders of $\phi$ and $-1/\phi$. Some case escaped me. Exiting back left... – Jyrki Lahtonen Sep 20 '13 at 19:29
  • @MarkBennet Thank you, the first part of your observation was what I was missing :) – N. S. Sep 20 '13 at 19:37

1 Answers1

5

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

N. S.
  • 132,525
  • 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. – awwalker 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
  • @user2566092 Added a solution to that too :) – N. S. Sep 20 '13 at 19:37
  • @Jyrki: Ah, of course. Silly me. – Harald Hanche-Olsen Sep 20 '13 at 19:54
  • This is VERY nice. – Jyrki Lahtonen Sep 20 '13 at 20:06