In mathematics, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and (where mod refers to the modulo operation).
The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem.
Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p).
A slightly stronger test uses the Jacobi symbol to predict which of the two results will be found.
The resultant Euler-Jacobi probable prime test verifies that As with the basic Euler test, a and n are required to be comprime, but that test is included in the computation of the Jacobi symbol (a/n), whose value equals 0 if the values are not coprime.