Relación entre los primos y la secuencia de Fibonacci

Question

Hace poco me topé con una relación inesperada entre los números primos y la secuencia de Fibonacci. Sabemos mucho sobre los números de Fibonacci, pero relativamente poco sobre los primos, así que merece la pena explorar esta conexión. Me interesa saber si alguien conoce un teorema o una prueba de si esta relación se cumple en general para los primos > 5 -- Lo he probado empíricamente para los primeros 100k primos usando Mathematica, pero eso no es una prueba.

$$ S_n = GCD(n, Fib(n+1)) $$ Si evaluamos esto para $n ~ in ~{1..100}$ nos encontramos con que:

{1, 2 , 3 , 1, 1, 1, 7 , 2, 1, 1, 1, 1, 13 , 2, 3, 1, 17 , 1, 1, 2, 1, 1, 23 , 1, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 37 , 2, 3, 1, 1, 1, 43 , 2, 1, 1, 47 , 1, 1, 2, 3, 1, 53 , 1, 1, 2, 1, 1, 1, 1, 1, 2, 21, 1, 1, 1, 67 , 2, 1, 1, 1, 1, 73 , 2, 3, 1, 1, 1, 1, 2, 1, 1, 83 , 1, 1, 2, 3, 1, 1, 1, 1, 2, 1, 1, 1, 1, 97 , 2, 33, 1}

Lo interesante de este resultado es que los primos aparecen en sus índices naturales: 2 aparece en $n_2$ , 13 aparece en $n_{13}$ , 83 aparece en $n_{83}$ y así sucesivamente. Pero faltan algunos de los primos, incluyendo:

{5, 11, 19, 29, 31, 41, 59, 61, 71, 79, 89}

Pero examinemos también la secuencia: $$ P_n = GCD(n, Fib(n-1)) $$

Aquí encontramos que en los primeros 100 términos obtenemos:

{1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 11 , 1, 1, 1, 1, 2, 1, 1, 19 , 1, 3, 2, 1, 1, 1, 1, 1, 2, 29 , 1, 31 , 1, 3, 2, 1, 1, 1, 1, 1, 2, 41 , 1, 1, 1, 3, 2, 1, 1, 7, 1, 1, 2, 1, 1, 1, 1, 3, 2, 59 , 1, 61 , 1, 1, 2, 1, 1, 1, 1, 3, 2, 71 , 1, 1, 1, 1, 2, 1, 13, 79 , 1, 3, 2, 1, 1, 1, 1, 1, 2, 89 , 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 2}

Si combinamos las secuencias $S_n$ y $P_n$ parece que conseguimos todos los primos, excepto el 5:

{2, 3, ( Falta : 5), 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}

A continuación se muestra un sencillo programa de Mathematica que prueba esto para los primeros miles de valores:

fibSuc[x_] := GCD[n, Fibonacci[n + 1]];
fibPre[x_] := GCD[n, Fibonacci[n - 1]];
fibPRZ[w_, fp_] :=
  (Cases[Select[Transpose[{Table[fp[n], {n, 1, w}], 
     Table[x, {x, 1, w}]}], PrimeQ[#1[[2]]] & ], {a_, a_}]) /. {a_, a_} -> a;
genPrimes[z_] := Union[fibPRZ[z, fibSuc], fibPRZ[z, fibPre]];

With[{pz = genPrimes[50000]},
   Complement[Table[Prime[n], {n, 1, Length[pz] + 1}], pz]]

Answer 1

Para los primos $p > 5$ se aplica la fórmula de Binet mod $p$ en el siguiente sentido. Si $p \equiv \pm 1 \mod 5$ , $5$ es un residuo cuadrático mod $p$ y $z^2 - z - 1$ tiene dos raíces $\phi_\pm = (1 \pm \sqrt{5})/2$ en ${\mathbb Z}_p$ . Entonces $F_n \equiv ((\phi_+^n - \phi_-^n)/\sqrt{5} \mod p$ . En particular, $F_{p-1}$ es divisible por $p$ Así que $\gcd(p, F_{p-1}) = p$ .

Si $p \equiv \pm 2 \mod 5$ , $z^2 - z - 1$ no tiene raíces en ${\mathbb Z}_p$ , pero tiene raíces en un campo de extensión $GF(p^2)$ . En este caso resulta que $F_{p+1}$ es divisible por $p$ Así que $\gcd(p, F_{p+1}) = p$ .

EDITAR: Obsérvese que tenemos $\phi_+ + \phi_- = 1$ y $\phi_+ \phi_- = -1$ . Ya que estamos en la característica $p$ , $\phi_+^p + \phi_-^p = 1^p = 1$ y $\phi_+^p\phi_-^p = (-1)^p = -1$ también. Así que $\phi_+^p$ y $\phi_-^p$ también son raíces de $z^2 - z - 1$ . Pero sólo hay dos raíces de este tipo. En el segundo caso, no podemos tener $\phi_+^p = \phi_+$ porque sólo los elementos de ${\mathbb Z}_p$ tienen la propiedad $z^p = z$ , por lo que debemos tener $\phi_+^p = \phi_-$ , y de forma similar $\phi_-^p = \phi_+$ . Entonces $$F_{p+1} = \dfrac{\phi_+^{p+1} - \phi_-^{p+1}}{\sqrt{5}} = \dfrac{\phi_- \phi_+ - \phi_+ \phi_-}{\sqrt{5}} = 0 \ \text{(as a member of $ GF(p^2) $)}$$ es decir $F_{p+1} \equiv 0 \mod p$ .

Answer 2

Me gustaría señalar que $p$ no puede dividir $F_{p}$ salvo quizás en el caso de $p=5$ . Su indexación podría estar fuera de uno; por ejemplo, $83 | F_{84}$ no $F_{83}$ como usted sugiere con la notación $n_{83}$ .

En general, si $p$ es un primo, entonces $p|F_{p-1}$ o $p|F_{p+1}$ pero no ambos. Si, por ejemplo, usted considera $p = 83$ entonces $83 | F_{84}$ y por lo tanto debe seguirse que $gcd(83, F_{84}) = 83$ para $83$ no tiene más factores primos que él mismo. El estudio de la sucesión de Fibonacci quizá se vea facilitado por un estudio en profundidad de las secuencias de Lucas, ya que la sucesión de Fibonacci no es más que una de las secuencias de Lucas.