In number theory, an odd integer n is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base a, if a and n are coprime, and where
The Jacobi symbol evaluates to 0 if a and n are not coprime, so the test can alternatively be expressed as: If n is an odd composite integer that satisfies the above congruence, then n is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base a.
As long as a is not a multiple of n (usually 2 ≤ a < n), then if a and n are not coprime, n is definitely composite, as 1 < gcd(a,n) < n is a factor of n. The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Euler's criterion article.
Solovay and Strassen showed that for every composite n, for at least n/2 bases less than n, n is not an Euler–Jacobi pseudoprime.
There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·109 (see OEIS: A047713) (page 1005 of [2]).