Fibonacci pseudoprimos

Question

Descubrí que los números de Fibonacci $F_n$, tomados $ \bmod n$, tienen la propiedad de que, para un primo $n\ne 5$, $F_{n-1}$ y $F_{n+1}$ son $0$ y $1, con el orden dependiendo del valor de $n\bmod 5$.

Por lo tanto, si un primo $n\equiv \pm 1\bmod 5$, $F_{n-1}\equiv 0$ y $F_{n+1}\equiv 1 \bmod n
Si un primo $n\equiv \pm 2\bmod 5$, $F_{n-1}\equiv 1$ y $F_{n+1}\equiv 0 \bmod n

También resulta ser una prueba bastante confiable de si $n$ es primo; es decir, no hay muchos compuestos que pasen la prueba. El primer número compuesto que se hace pasar por primo es $4181$, luego $5777, 6721, 10877, 13201, 15251$ son los seudoprimos restantes por debajo de $20000$. Esta secuencia se encuentra en OEIS A212424.

Lo que no he podido hacer es demostrar que esta propiedad realmente se cumple para los números primos. ¿Alguien puede producir una prueba de la veracidad de esta relación?

---

Greg Martin dio algunos términos útiles:

La primera enteros positivo $m$ para el cual $F_m\equiv 0 \bmod n$ se llama el "rango de aparición" de $n$

Luego ($\equiv \bmod n$) el "multiplicador de aparición" (mi término) $k:\equiv F_{m-1}\equiv F_{m+1}\equiv F_{m+2}$ significa que $F_{i+m}\equiv k F_i$ y $F_{i+jm}\equiv k^j F_i$. $k$ debe ser coprimo a $n$ porque la secuencia de Fibonacci se puede generar al revés, así que algún $d\ne 1$ que divida tanto a $k$ como a $n$ excluiría $F_1=1$ (ya que $d$ dividiría cada elemento). Esto garantiza que $F_s\equiv 0 \Rightarrow m\mid s$ y que en algún momento, dado que $k^j\equiv 1$, tendremos el periodo $r, \bmod n.

Para el resultado anterior en números primos necesitamos $r\mid n{-}1$ en el primer caso y $m\mid n{+}1, r\mid 2(n{+}1)$ en el segundo caso.

Todavía estaba pensando en qué valores puede tomar el rango de aparición $m$ y trabajando en http://www.fq.math.ca/Scanned/1-2/vinson.pdf.

Answer 1

Si $p \equiv \pm 1 \pmod 5$ entonces $x^2-x-1$ se factoriza como $(x-\phi)(x-\overline{\phi})$ en $\mathbb{F}_p$. Luego, tus identidades se siguen de $$F_n\equiv \frac{\phi^n-\overline{\phi}^n}{\phi - \overline{\phi}} \pmod p$$ ya que en este caso $\phi^{p-1}\equiv 1$ (por Fermat) y $$\phi^{p+1}\equiv \phi^2 \equiv \phi+1$$ y lo mismo para $\overline{\phi}$.

Si $p\equiv \pm 2 \pmod 5$ entonces el mismo polinomio se factoriza en $\mathbb{F}_{p^2}$ y el automorfismo de Frobenius intercambia las raíces. Es decir, $\phi^p=\overline{\phi}$ y $\overline{\phi}^p=\phi$. Tus identidades ahora se siguen de $$\phi^{p-1}\equiv \overline{\phi} \phi^{-1} \equiv -\overline{\phi}^2 \equiv -\overline{\phi}-1$$ y $$\phi^{p+1}\equiv \overline{\phi} \phi \equiv -1$$ y lo mismo para $\overline{\phi}$.