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.el n-ésimo número de Fermat.El test de Pépin establece que para cada n > 0, La expresiónse puede evaluar móduloelevá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).Para la demostración en un sentido, se parte de la congruencia Entonces,, por tanto, el orden multiplicativo de 3 módulo, que es una potencia de dos.Por otra parte, el orden no divide a, por lo que debe ser igual aEn particular, existen al menosnúmeros menores queque son coprimos con, y esto sólo puede ocurrir siPara el otro sentido, supóngase quePor el criterio de Euler, dondees el símbolo de Legendre.Elevándolo al cuadrado repetidas veces, encontramos quedebido a la ley de reciprocidad cuadrática.