Inmathematics, anoddcompositeintegern is called anEuler pseudoprime to basea, ifa andn arecoprime, and

${\displaystyle a^{(n-1)/2}\equiv \pm 1(\mathrm{mod}n)}$

(wheremod refers to themodulo operation).

The motivation for this definition is the fact that allprime numbersp satisfy the above equation which can be deduced fromFermat's little theorem. Fermat's theorem asserts that ifp is prime, and coprime toa, thena^p−1 ≡ 1 (modp). Suppose thatp>2 is prime, thenp can be expressed as 2q + 1 whereq is an integer. Thus,a^{(2q+1) − 1} ≡ 1 (mod p), which means thata^2q − 1 ≡ 0 (modp). This can be factored as (a^q − 1)(a^q + 1) ≡ 0 (modp), which is equivalent toa^(p−1)/2 ≡ ±1 (mod p).

The equation can be tested rather quickly, which can be used for probabilisticprimality testing. These tests are twice as strong as tests based on Fermat's little theorem.

Every Eulerpseudoprime is also aFermat pseudoprime. It is not possible to produce a definite test of primality based on whether anumber is an Euler pseudoprime because there existabsolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are asubset of the absolute Fermat pseudoprimes, orCarmichael numbers, and the smallest absolute Euler pseudoprime is1729 = 7×13×19 (sequenceA033181 in theOEIS).

A slightly stronger test uses theJacobi symbol to predict which of the two results will be found. The resultantEuler-Jacobi probable prime test verifies that

${\displaystyle a^{(n-1)/2}\equiv \left(\frac{a}{n}\right)\ne 0(\mathrm{mod}n).}$

As with the basic Euler test,a andn 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 arenot coprime. This slightly stronger test is called simply an Euler probable prime test by some authors. See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.^[1]

As an example of this test's increased strength, 341 is an Euler pseudoprime to the base 2, but not an Euler-Jacobi pseudoprime. Even more significantly, there are no absolute Euler–Jacobi pseudoprimes.^[1]: 1004

Astrong probable prime test is even stronger than the Euler-Jacobi test but takes the same computational effort. Because of this, prime-testing software is usually based on the strong test.

function EulerTest(k)  a = 2if k == 1then return falseelseif k == 2then return trueelse    m =modPow(a,(k-1)/2,k)if (m == 1) or (m == k-1)thenreturn trueelsereturn falseendendend

• Probable prime

• M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
• H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.

• Pseudoprimes

• Articles with short description
• Short description matches Wikidata