En aritmética, un número entero compuesto impar n se llama pseudoprimo de Euler en base a, si a y n son números coprimos, y (donde mod se refiere a la operación módulo).
La motivación de esta definición es el hecho de que todos los números primos p satisfacen la ecuación anterior que puede deducirse del pequeño teorema de Fermat, que afirma que si p es primo y coprimo de a, entonces ap−1 ≡ 1 (mod p).
Entonces, p se puede expresar como 2q + 1 donde q es un número entero.
No hay pseudoprimos absolutos de Euler-Jacobi.[1]: p.
1004 La prueba de un probable primo fuerte es incluso más fuerte que la prueba de Euler-Jacobi, pero requiere el mismo esfuerzo computacional.