La naturaleza periódica de la secuencia de Fibonacci módulo $m$

Question

Sea $x_n$ el $n$-ésimo elemento de la sucesión de Fibonacci y $$A:=\begin{pmatrix} 0&1\\1&1 \end{pmatrix}$$ Es fácil de demostrar que se cumple: $$A^n=\begin{pmatrix} F_{n-1}&F_n\\F_n&F_{n+1} \end{pmatrix}$$ Sin embargo, quiero demostrar que $$(F_n\text{ mod }m)_n\;\;\;\;\;(m\in\mathbb{N})$$ es una secuencia periódica. Por lo tanto, es suficiente mostrar que $$(A^n\text{ mod }m)_n$$ es periódica. En otras palabras: Necesitamos demostrar que $A$ es un elemento de orden finito en $\text{GL}(2,\mathbb{Z}/m\mathbb{Z})$. ¿Cuál es la forma más elegante de hacerlo?

PD: Sé que podría ser mejor elegir $A$ y por lo tanto $A^n$ de otra manera, pero me piden que demuestre la afirmación para la elección dada de $A$.

Answer 1

Hay m residuos módulo m. Por lo tanto, hay a lo sumo $m^2$ combinaciones de la suma de dos de esos residuos. Dado que cada número de Fibonacci comienza con 0 módulo m y hay un número infinito de números de Fibonacci, eventualmente son periódicos módulo m para todo m natural.

Answer 2

Robert tiene razón, la pregunta planteada no se aborda completamente. Aquí intentaré demostrar que la secuencia de Fibonacci es periódica módulo un primo $p$ cuando $\left(\frac{5}{p}\right)=1.

Dado que $5$ es un residuo, el polinomio $x^2-x-1$ se descompone en $F_p$ y tiene raíces $\alpha, \beta$. Así que podemos encontrar constantes $A, B \in F_p$ tales que: $$ f_n \equiv_p A\alpha^n+B\beta^n $$ entonces $$ f_{n+k(p-1)}= A\alpha^{n+k(p-1)} + B\beta^{n+k(p-1)}\\ = f_n $$ ya que $\alpha^{p-1} = \beta^{p-1} = 1$

por lo tanto $f_n$ es periódica con un período que es un divisor de $p-1$

como ejemplo $$ f_n \equiv_{11} 2(8^n) + 10(4^n) $$