Números de Fibonacci módulo $p$

Question

Si $p$ es primo, entonces $F_{p-\left(\frac{p}{5}\right)}\equiv 0\bmod p$ , donde $F_j$ es el $j$ número de Fibonacci, y $\left(\frac{p}{5}\right)$ es el símbolo de Jacobi.

¿Quién lo demostró por primera vez? ¿Existe una demostración lo suficientemente sencilla para un curso de teoría de números de licenciatura? (Llegaremos a la reciprocidad cuadrática al final del trimestre).

Answer 1

Recomiendo el capítulo XVII del volumen 1 de la Historia de la teoría de los números de Dickson. Cita resultados de Legendre, Gauss, Dirichlet y Lagrange, entre otros, ninguno de ellos exactamente el que citas, pero todos ellos muy relacionados, y más generales.

Hardy y Wright dan dos pruebas. Es el Teorema 180 en el capítulo sobre fracciones continuas, y luego hay otra prueba al final de la sección 4 del Capítulo 15, Campos Cuadráticos.

Véase también el teorema 4.12 de Niven, Zuckerman y Montgomery.

Answer 2

La cónica de Pell $\mathcal{C} : x^2 - 5 y^2 = 4$ tiene $p - (5/p)$ puntos modulo $p$ . Los polinomios $$f_{-1} = x, f_0 = 2, f_n = x f_{n-1} - f_{n-2}$$ $$g_{-1} = -1, g_0 = 0, g_n = x g_{n-1} - g_{n-2}$$ realizar la multiplicación por $n$ en el grupo $\mathcal{C}(\mathbb{F}_p)$ , $n (x, y) = (f_n(x), y \cdot g_n(x))$ . Dejemos que $P = (3, 1) \in \mathcal{C}(\mathbb{F}_p)$ . Observe que $g_n(3)$ es el $n+2$ -número de Fibonacci. De ello se deduce que $$(p - (5/p))P \equiv (2, 0) \pmod{p}$$ desde $(2,0)$ es el elemento de identidad.

Answer 3

Aquí hay una prueba que sólo utiliza un poco de teoría de Galois de campos finitos (y QR). No sé si es alguna de las pruebas a las que hace referencia Gerry. Recordemos que $$F_n = \frac{\phi^n - \varphi^n}{\phi - \varphi}$$

donde $\phi, \varphi$ son las dos raíces de $x^2 = x + 1$ . Lo más importante es que esta fórmula sigue siendo válida en $\mathbb{F}_{p^2}$ donde $p$ es cualquier primo tal que $x^2 = x + 1$ tiene raíces distintas, por lo que cualquier primo que no sea igual a $5$ . Distinguimos dos casos:

• $x^2 = x + 1$ es irreducible. Esto es cierto para $p = 2$ y para $p > 2, p \neq 5$ es verdadera si y sólo si el discriminante $\sqrt{5}$ no es un cuadrado $\bmod p$ Por lo tanto, si y sólo si $\left( \frac{5}{p} \right) = -1$ por lo tanto, por QR si y sólo si $\left( \frac{p}{5} \right) = -1$ . En este caso $x^2 = x + 1$ se divide en $\mathbb{F}_{p^2}$ y el mapa de Frobenius $x \mapsto x^p$ genera su grupo de Galois, por lo que $\phi^p \equiv \varphi \bmod p$ . De ello se desprende que $\phi^{p+1} \equiv \phi \varphi \equiv -1 \bmod p$ y lo mismo ocurre con $\varphi$ por lo que $F_{p+1} \equiv 0 \bmod p$ .

• $x^2 = x + 1$ es reducible. Esto es falso para $p = 2$ y para $p > 2, p \neq 5$ es cierto si y sólo si $\left( \frac{p}{5} \right) = 1$ . En este caso $x^2 = x + 1$ se divide en $\mathbb{F}_p$ Por lo tanto $\phi^{p-1} \equiv 1 \bmod p$ y lo mismo ocurre con $\varphi$ Por lo tanto $F_{p-1} \equiv 0 \bmod p$ .

El caso $p = 5$ pueden ser manejados por separado. Sin embargo, esto es un poco feo.