The periodic nature of the fibonacci sequence modulo $m$

Question

Let $x_n$ denote the $n$-th element of the fibonacci sequence and $$A:=\begin{pmatrix} 0&1\\1&1 \end{pmatrix}$$ It's easy to show, that it holds: $$A^n=\begin{pmatrix} F_{n-1}&F_n\\F_n&F_{n+1} \end{pmatrix}$$ However, I want to show that $$(F_n\text{ mod }m)_n\;\;\;\;\;(m\in\mathbb{N})$$ is a periodic sequence. Therefor, it's sufficient to show, that $$(A^n\text{ mod }m)_n$$ is periodic. In other words: We need to show, that $A$ is an element of finite order in $\text{GL}(2,\mathbb{Z}/m\mathbb{Z})$. What's the most elegant way to do that?

PS: I know that it might be better to choose $A$ and thereby $A^n$ in an other way, but I'm asked to show the statement for the given choice of $A$.

Answer 1

There are m residues modulo m. Therefore, there are atmost $m^2$ combinations of the sum of two of those residues. Since each Fibonacci number stars 0 modulo m and there are an infinite number of Fibonacci numbers, they are eventually periodic modulo m for all natural m.

Answer 2

Robert is right, the question as posed is not completely dealt with. here i will attempt to show the Fibonacci sequence is periodic modulo a prime $p$ when $\left(\frac{5}{p}\right)=1$.

since $5$ is a residue the polynomial $x^2-x-1$ splits in $F_p$ and has roots $\alpha,\beta$. thus we may find constants $A,B \in F_p$ such that: $$ f_n \equiv_p A\alpha^n+B\beta^n $$ thus $$ f_{n+k(p-1)}= A\alpha^{n+k(p-1)} + B\beta^{n+k(p-1)}\\ = f_n $$ since $\alpha^{p-1} = \beta^{p-1} = 1$

thus $f_n$ is periodic with period a divisor of $p-1$

as an example $$ f_n \equiv_{11} 2(8^n) + 10(4^n) $$