Jump to content

Euler pseudoprime

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Michael Hardy (talk | contribs) at 17:39, 23 July 2004 (The article titled modulo is not mainly about modular arithmetic; fixing the link.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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). 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 a2q - 1 = 0 (mod p). This can be factored as (aq - 1)(aq + 1) = 0 (mod p) which is equivalent to a(p-1)/2 = ±1 (mod p).

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

Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, 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-1)/2 = (a/n) (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: