Número pseudoprimo de Euler-Jacobi
# Número pseudoprimo de Euler-Jacobi

En teoría de números, un número entero impar n se denomina primo probable de Euler-Jacobi (o, más comúnmente, primo probable de Euler) en base a, si a y n son números coprimos, y

    $a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

donde $\left({\frac {a}{n}}\right)$ es el símbolo de Jacobi.

Si n es un entero compuesto impar que satisface la congruencia anterior, entonces n se denomina número pseudoprimo de Euler-Jacobi' (o, más comúnmente, pseudoprimo de Euler) respecto a la base a.

## Propiedades

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 dedicado al criterio de Euler. La ecuación se puede probar con bastante rapidez, lo que se puede usar para realizar 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.

Cada pseudoprimo de Euler-Jacobi es también un pseudoprimo de Fermat y un pseudoprimo de Euler. No hay 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úmero compuesto n, para al menos n/2 bases menores que n, n no es un pseudoprimo de Euler-Jacobi.

El pseudoprimo de base 2 de Euler-Jacobi más pequeño es 561. Hay 11347 pseudoprimos de base 2 de Euler-Jacobi que son menores que 25 · $10^9$ (véase (sucesión A047713 en OEIS)) y la página 1005 de The pseudoprimes to $25·10^9).$

En la literatura (por ejemplo, en el texto mencionado), un pseudoprimo de Euler-Jacobi como se definió anteriormente a menudo se denomina simplemente pseudoprimo de Euler.

