Ciclos en la secuencia generalizada de Fibonacci módulo a un primo

Question

Supongamos que tengo una secuencia de fibonacci

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584

Ahora bien, si tengo una secuencia de fibonacci módulo 5, se verá como

0 1 1 2 3 0 3 3 1 4 0 4 4 3 2 0 2 2 4 1 0 1 1 2 3 0 3 3 1

Si tengo la secuencia de fibonacci de módulo 7 se verá como

0 1 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1 1 2 3 5 1 6 0 6 6 5 4 2 6 

Ahora, notamos que el patrón se repite en la secuencia modular de Fibonacci. Quiero saber cuál es el punto en el que el patrón comienza a repetirse, es decir, cuál es la relación de la posición de inicio de la repetición con el número modular como 5, 7, 11, etc.

Por favor, manténgalo lo más simple posible.Tengo que usar este concepto en un algoritmo

EDITAR Investigando un poco he encontrado este como respuesta,pero implica muchas matemáticas que no puedo entender.Puede alguien por favor descifrarlo y darme una expresión directa

Answer 1

Se refiere a la Período de Pisano . No hay otra forma de calcular esto que no sea el cálculo directo. Sin embargo, se puede un período que puede ser, pero no es necesariamente, el período mínimo.

Denotando el período de la secuencia de Fibonacci módulo $p$ como $\pi(p)$ , con un primo $p\neq 5$ podemos encontrar que $F_{p-\left(\frac{p}{5}\right)}\equiv 0\,(\bmod\, p)$ y $F_p \equiv \left(\frac{p}{5}\right)(\bmod\, p)$ , donde $\left(\frac{p}{5}\right)$ es un símbolo de Legendre.

En otras palabras,

• Si $p \equiv \pm 1 \,(\bmod \,5)$ entonces tenemos que $F_{p-1}\equiv 0\,(\bmod\, p)$ y $F_p \equiv 1\,(\bmod\, p)$ para que $p-1$ marca el inicio de la primera repetición de la secuencia. Por lo tanto, $\pi(p) \mid p - 1$
• En caso contrario, si $p \equiv \pm 2 \,(\bmod \,5)$ entonces $F_{p+1}\equiv 0\,(\bmod\, p)$ y $F_{p}\equiv p-1\,(\bmod\, p)$ . A partir de esto, podemos encontrar que $F_{2p+1} \equiv 1\,(\bmod\, p)$ y $F_{2p+2}\equiv 0\,(\bmod\, p)$ . Por lo tanto, $F_{2p+3}\equiv 1\,(\bmod\, p)$ y tenemos una periodicidad de $2p + 2$ - es decir, $\pi(p) \mid 2(p+1)$ .

Así que $p-1$ y $2(p+1)$ pueden servir como periodicidades efectivas para cada caso, respectivamente.

Aquí hay una buen papel con una exposición más básica.