Euler pseudoprime

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 a^p-1 = 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q+1 where q is an integer. Thus; a^(2q+1)-1 = 1 (mod p) which means that a^2q - 1 = 0 (mod p). This can be factored as (a^q - 1)(a^q + 1) = 0 (mod p) which is equivalent to a^{(p-/sup> = ±1 (mod pprimality testingpseudoprimenumber, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 561 = 3·11·17.}

It should be noted that the stronger condition that a^{(n-/sup> = (an) (mod n), where (a,n)=1 and (a/n) is the Jacobi symbol, is sometimes used for a definition of an Euler pseudoprime. A discussion of numbers of this form can be found at Euler-Jacobi pseudoprime.}

See also:

• Probable prime