Proof that Fibonacci Sequence modulo m is periodic? [duplicate]

It's well known that the Fibonacci sequence $\pmod m$ (where $m \in \mathbb N$) is periodic. I have figured out a proof for this, but upon googling, I found proofs online that were far more complicated. This leads me to suspect that my proof may be fallacious - that's why I am posting here.

Proof:

Let us list out the Fibonacci sequence modulo m, where m is some integer. It will look something like this at first (for $10$ at least):

$$ 1,2, 3,5,8, 3,1, 4, 5, 9, 4, 3, 7 {\dots}$$

Obviously, any number in the sequence is the sum of the last two numbers modulo $m$. Therefore, if at any point in the series modulo m a pair of numbers repeat, the numbers following that pair must repeat as well. eg. if at some point later we see the pair $1, 1$, then $2, 3, 5, \dots$ must follow that pair.

Now there are $m^2$ possible pairs in the series $\text{mod} m$. By the pigeonhole principle, after $m^2 + 1$ terms, a pair must repeat. If a pair repeats once, it must repeat again the same number of terms later. Therefore, the Fibonacci sequence $\pmod m$ is periodic $\forall m$ .

Is my proof correct?

Solution 1:

No, you haven't proven yet that the Fibonacci sequence is periodic ($\exists t, \forall n, F(n+t) = F(n)$), you have proven that it is eventually periodic ($\exists t, \exists n, \forall m, m \ge n \implies F(m+t) = F(m)$)

If you have a finite set $S$ (here, the set of pairs modulo $m$) and a function $f :S \to S$, any sequence obtained by iterating $f$ on some element of $S$ is eventually periodic, by the pigeonhole principle. If you want every such sequence to be periodic, you need $f$ to be a bijection :

If $f$ is a bijection and $F(n+1+t) = F(n+1)$ for some $n$, then by applying $f^{-1}$ we get $F(n+t) = F(n)$, and we repeat until we obtain $F(t) = F(0)$.

If $f$ is not bijective, it is not surjective, so if you start your sequence on some element not in the image of $f$, it will never be periodic because that element can't appear again in the sequence.

Here, $f(a,b) = (b,a+b)$, which is a bijection because its inverse is given by $f^{-1}(a,b) = (b-a,a)$