En teoría de números , un entero impar n se denomina primo probable de Euler-Jacobi (o, más comúnmente, primo probable de Euler ) con base a , si a y n son coprimos , y
donde es el símbolo de Jacobi . El símbolo de Jacobi se evalúa como 0 si a y n no son coprimos, por lo que la prueba se puede expresar alternativamente como:
Si n es un entero compuesto impar que satisface la congruencia anterior, entonces n se denomina pseudoprimo de Euler–Jacobi (o, más comúnmente, pseudoprimo de Euler ) para basar a .
Siempre que a no sea un múltiplo de n (normalmente 2 ≤ a < n ), entonces si a y n no son coprimos, n es definitivamente compuesto, ya que 1 < mcd ( a , n ) < n es un factor de n .
La motivación de esta definición es el hecho de que todos los números primos n satisfacen la ecuación anterior, como se explica en el artículo sobre el criterio de Euler . La ecuación se puede probar con bastante rapidez, lo que se puede utilizar para pruebas de primalidad probabilísticas . Estas pruebas son más del doble de sólidas que las pruebas basadas en el pequeño teorema de Fermat .
Todo pseudoprimo de Euler-Jacobi es también un pseudoprimo de Fermat y un pseudoprimo de Euler . No existen números que sean pseudoprimos de Euler-Jacobi en todas las bases como lo son los números de Carmichael . Solovay y Strassen demostraron que para cada n compuesto , para al menos n /2 bases menores que n , n no es un pseudoprimo de Euler-Jacobi. [1]
El pseudoprimo de Euler–Jacobi base 2 más pequeño es 561. Hay 11347 pseudoprimos de Euler–Jacobi base 2 que son menores que 25·10 9 (ver OEIS : A047713 ) (página 1005 de [2] ).
En la literatura (por ejemplo, [2] ), un pseudoprimo de Euler–Jacobi como el definido anteriormente a menudo se denomina simplemente pseudoprimo de Euler.
Función EulerJacobiTest(k) a = 2 si k == 1 entonces devuelve falso de lo contrario si k == 2 entonces devuelve verdadero de lo contrario si ( modPow(a,(k-1)/2,k) == Jacobi(a,k) ) entonces devuelve verdadero de lo contrario devuelve falso fin fin fin
