La prueba de Pepin

En matemáticas , la prueba de Pépin es una prueba de primalidad , que puede usarse para determinar si un número de Fermat es primo . Es una variante del test de Proth . La prueba lleva el nombre de un matemático francés, Théophile Pépin .

Descripción de la prueba

Sea el enésimo número de Fermat. La prueba de Pépin establece que para n > 0, ${\displaystyle F_{n}=2^{2^{n}}+1}$

${\displaystyle F_{n}}$es primo si y solo si ${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}.}$

La expresión se puede evaluar módulo elevando al cuadrado repetidamente . Esto hace que la prueba sea un algoritmo rápido de tiempo polinomial . Sin embargo, los números de Fermat crecen tan rápidamente que sólo un puñado de números de Fermat pueden probarse en un tiempo y espacio razonables. ${\displaystyle 3^{(F_{n}-1)/2}}$ ${\displaystyle F_{n}}$

Se pueden usar otras bases en lugar de 3. Estas bases son:

3, 5, 6, 7, 10, 12, 14, 20, 24, 27, 28, 39, 40, 41, 45, 48, 51, 54, 56, 63, 65, 75, 78, 80, 82, 85, 90, 91, 96, 102, 105, 108, 112, 119, 125, 126, 130, 147, 150, 156, 160,... (secuencia A129802 en el OEIS ).

Los números primos en la secuencia anterior se llaman números primos de élite y son:

3, 5, 7, 41, 15361, 23041, 26881, 61441, 87041, 163841, 544001, 604801, 6684673, 14172161, 159318017, 446960641, 1, 3208642561, 38126223361, 108905103361, 171727482881, 318093312001, 443069456129, 912680550401, .. (secuencia A102742 en la OEIS ) .

Para un entero b > 1, la base b se puede usar si y solo si solo un número finito de números de Fermat F _n satisface que , donde está el símbolo de Jacobi . ${\displaystyle \left({\frac {b}{F_{n}}}\right)=1}$ ${\displaystyle \left({\frac {b}{F_{n}}}\right)}$

De hecho, la prueba de Pépin es la misma que la prueba de Euler-Jacobi para los números de Fermat, ya que el símbolo de Jacobi es −1, es decir, no hay números de Fermat que sean pseudoprimos de Euler-Jacobi con respecto a estas bases enumeradas anteriormente. ${\displaystyle \left({\frac {b}{F_{n}}}\right)}$

Prueba de corrección

Suficiencia: asumir que la congruencia

${\displaystyle 3^{(F_{n}-1)/2}\equiv -1{\pmod {F_{n}}}}$

sostiene. Entonces , así el orden multiplicativo de 3 módulo divide , que es una potencia de dos. Por otro lado, el orden no divide y por tanto debe ser igual a . En particular, hay al menos números por debajo de coprimos , y esto sólo puede suceder si es primo. ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$ ${\displaystyle F_{n}}$ ${\displaystyle F_{n}-1=2^{2^{n}}}$ ${\displaystyle (F_{n}-1)/2}$ ${\displaystyle F_{n}-1}$ ${\displaystyle F_{n}-1}$ ${\displaystyle F_{n}}$ ${\displaystyle F_{n}}$ ${\displaystyle F_{n}}$

Necesidad: asumir que es prima. Según el criterio de Euler , ${\displaystyle F_{n}}$

${\displaystyle 3^{(F_{n}-1)/2}\equiv \left({\frac {3}{F_{n}}}\right){\pmod {F_{n}}}}$,

¿Dónde está el símbolo de Legendre ? Al elevar al cuadrado repetidamente, encontramos que , por lo tanto , y . Como , concluimos de la ley de reciprocidad cuadrática . ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$ ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$ ${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$ ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$ ${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$

Pruebas históricas de Pépin

Debido a la escasez de los números de Fermat, la prueba de Pépin sólo se ha ejecutado ocho veces (en números de Fermat cuyo estado de primalidad aún no se conocía). ^{[1] [2] [3]} Mayer, Papadopoulos y Crandall especulan que, de hecho, debido al tamaño de los números de Fermat aún indeterminados, serán necesarios avances tecnológicos considerables antes de que se puedan realizar más pruebas de Pépin en una cantidad razonable de tiempo. tiempo. ^[4]

Notas

1. Conjetura 4. Los primos de Fermat son finitos: historia de las pruebas de Pepin, según Leonid Durman
2. Wilfrid Keller: estado de factoraje de Fermat
3. RM Robinson (1954): Números de Mersenne y Fermat, doi :10.2307/2031878
4. Richard E. Crandall, Ernst W. Mayer y Jason S. Papadopoulos (2003): El vigésimo cuarto número de Fermat es compuesto, doi :10.1090/S0025-5718-02-01479-5

Referencias

• P. Pépin, Sur la formule ${\displaystyle 2^{2^{n}}+1}$ , Comptes rendus de l'Académie des Sciences de Paris 85 (1877), págs.

enlaces externos

• El primer glosario: la prueba de Pipino