Test de Pépin

En matemáticas, el test de Pépin (por el matemático francés P. Pépin) es un test de primalidad que se puede emplear para determinar si un número de Fermat es primo. Es una variante del test de Proth.

Descripción del test

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

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

La expresión ${\displaystyle 3^{(F_{n}-1)/2}}$ se puede evaluar módulo ${\displaystyle F_{n}}$ elevándolo repetidamente al cuadrado. Esto permite que el test tenga un tiempo de ejecución polinómico, es decir, en principio se trata de un algoritmo rápido. Sin embargo, los números de Fermat crecen tan rápidamente que sólo se pueden evaluar unos pocos en un intervalo de tiempo razonable.

También pueden emplearse otras bases en lugar de 3, por ejemplo, 5, 6, 7 o 10 (A129802).

Demostración de que el test funciona

Para la demostración en un sentido, se parte de la congruencia

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

Entonces, ${\displaystyle 3^{F_{n}-1}\equiv 1{\pmod {F_{n}}}}$, por tanto, el orden multiplicativo de 3 módulo ${\displaystyle F_{n}}$ divide a ${\displaystyle F_{n}-1=2^{2^{n}}}$, que es una potencia de dos. Por otra parte, el orden no divide a ${\displaystyle (F_{n}-1)/2}$, por lo que debe ser igual a ${\displaystyle F_{n}-1}$. En particular, existen al menos ${\displaystyle F_{n}-1}$ números menores que ${\displaystyle F_{n}}$ que son coprimos con ${\displaystyle F_{n}}$, y esto sólo puede ocurrir si ${\displaystyle F_{n}}$ es primo.

Para el otro sentido, supóngase que ${\displaystyle F_{n}}$ es primo. Por el criterio de Euler,

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

donde ${\displaystyle \left({\frac {3}{F_{n}}}\right)}$ es el símbolo de Legendre. Elevándolo al cuadrado repetidas veces, encontramos que ${\displaystyle 2^{2^{n}}\equiv 1{\pmod {3}}}$, por tanto, ${\displaystyle F_{n}\equiv 2{\pmod {3}}}$, y ${\displaystyle \left({\frac {F_{n}}{3}}\right)=-1}$. Como ${\displaystyle F_{n}\equiv 1{\pmod {4}}}$, concluimos que ${\displaystyle \left({\frac {3}{F_{n}}}\right)=-1}$ debido a la ley de reciprocidad cuadrática.

Referencias

• P. Pépin, Sur la formule ${\displaystyle 2^{2^{n}}+1}$, Comptes Rendus Acad. Sci. Paris 85 (1877), pp. 329–333.

Enlaces externos

• Caldwell, Chris. «The Prime Glossary: Pepin's test» (en inglés). The Prime Pages. Universidad de Tennessee. http://primes.utm.edu/glossary/page.php?sort=PepinsTest .