Secuencia de Fibonacci en $\mathbb Z_n$ .

Question

Considere una secuencia de Fibonacci, excepto en $\mathbb Z_n$ en lugar de $\mathbb Z$ :

$$F(1) = F(2) = 1$$ $$F(n+2) = F(n+1) + F(n)$$

Es fácil ver que cada una de estas secuencias debe recorrer alguna secuencia y repetirse. Consideremos, por ejemplo, la secuencia de $\mathbb Z_4$ :

$$1,1,2,3,1,0,1,1,2,3,1,0,\dots$$

¿Existe una forma agradable de describir la longitud de la secuencia que resulta antes de la repetición? Está claro que debe ser menor que $n^2$ ya que eso haría un ciclo a través de todas las combinaciones posibles de $a,b$ con $a,b \in \mathbb Z_n$ y una vez que se repiten dos combinaciones, se tiene un ciclo.

\begin{align*} \mathbb Z_2: 1,1,0,\dots & 3 \\ \mathbb Z_3: 1,1,2,0,2,2,1,0,\dots & 8 \\ \mathbb Z_4: 1,1,2,3,1,0,\dots & 6 \\ \mathbb Z_5: 1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,\dots & 20 \end{align*}

Examinando las secuencias anteriores, parece "obvio" que hay algún patrón (sólo hay que ver cómo $0$ se produce cada $5$ número). ¿Existe una forma "bonita" de describir estas secuencias (como una forma de calcular el $k^{th}$ término de una secuencia) y, en particular, una regla para las longitudes de los ciclos?

Answer 1

He encontrado una forma de hacerlo con prime $n.$ No estoy seguro de que se extienda a las primeras potencias.

Queremos saber qué pasa con el par de entradas consecutivas $(x,y),$ cambiando sobre uno para obtener $(y,x+y).$ Así que definimos la matriz $$ A \; = \; \left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) , $$ y nota $$ \left( \begin{array}{rr} 0 & 1 \\ 1 & 1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) \; = \; \left( \begin{array}{c} y \\ x+ y \end{array} \right) $$

Encontramos $A^2 = A + I,$ así como $A^{-1} = A - I.$ Como resultado, el conjunto de sumas de potencias de $A$ forman un anillo conmutativo; calculamos $$ A^3 = 2A + I, $$ $$ A^4 = 3A + 2I, $$ $$ A^5 = 5A + 3I, $$ $$ A^6 = 8A + 5I, $$ $$ A^7 = 13A + 8I, $$ $$ A^8 = 21A + 13I, $$ y así sucesivamente. No sabemos con seguridad que tenemos una repetición hasta que hayamos repetido el par $(x,y).$ A continuación, ¿qué pasa si consideramos los coeficientes de este anillo como elementos del campo $\mathbf Z / p \mathbf Z ?$

Nos gustaría saber cuál es el menor $m$ tal que $$ A^m \equiv I \pmod p. $$ Esto tiene dos partes. Primero ilustramos. $$ A^3 \equiv I \pmod 2. $$ $$ A^4 \equiv 2I \pmod 3, 2^2 \equiv 1 \pmod 3, A^8 \equiv I \pmod 3. $$ $$ A^5 \equiv 3I \pmod 5, 3^4 \equiv 1 \pmod 5, A^{20} \equiv I \pmod 5. $$ $$ A^8 \equiv 6I \pmod 7, 6^2 \equiv 1 \pmod 7, A^{16} \equiv I \pmod 7. $$ Para cada primo, el segundo exponente es un factor de $p-1,$ como $$ \lambda^{p-1} \equiv 1 \pmod p. $$

Antes me olvidé de un punto. Si $p \equiv 2,3 \pmod 5,$ entonces no hay soluciones para $x^2 - x - 1 \pmod p,$ la cosa es irreducible, y nuestro anillo de matrices es un campo con $p^2$ elementos. El conjunto de elementos no nulos es un grupo multiplicativo con $p^2 - 1$ elementos. De ello se desprende que, con nuestra $A^m \equiv I \pmod p,$ que $m | (p^2 - 1).$

Para $p = 5$ ou $p \equiv 1,4 \pmod 5,$ el anillo tiene divisores cero, dados explícitamente por los factores de $x^2 - x - 1 \pmod p$ y sus múltiplos escalares. Molesta. Por otro lado, para $p \equiv 1,4 \pmod 5$ parece que $A^{p-1} \equiv I \pmod p,$ verdadero para $p=11,19,29,31,41,$ y tal vez demostrable.

Desde el enlace dado en los comentarios anteriores sobre Períodos de Pisano Por fin entiendo cómo hacer $p \equiv 1,4 \pmod 5.$ Dejemos que $\phi$ sea cualquiera de las dos raíces distintas de $\phi^2 - \phi - 1 \equiv 0 \pmod p. $ Entonces, con la numeración $F_0 = 0, F_1 = 1, F_2 = 1, F_3 = 2, F_4 = 3, F_5 = 5,$ encontramos $$ F_n = \frac{\phi^n - (1-\phi)^n}{2 \phi - 1}. $$ Utilizando $a^{p-1} \equiv 1 \pmod p$ y $\phi^2 \equiv \phi + 1 \pmod p$ y $\frac{1}{\phi} \equiv \phi - 1 \pmod p,$ encontramos tanto $$ F_{p-1} \equiv 0 \pmod p, \; \; \; F_{p-2} \equiv 1 \pmod p. $$ De nuestra anterior discusión sobre la matriz $A,$ vemos que $$ A^n = F_n A + F_{n-1} I, $$ señalado más abajo por awllower. Así que $$ A^{p-1} = F_{p-1} A + F_{p-2} I \equiv I \pmod p. $$ Como resultado, cualquier secuencia de este tipo, Fibonacci o Lucas o lo que sea, se repite con periodo $p-1$ o algún divisor del mismo.