Euler-Jacobi pseudoprime

related topics
{math, number, function}

In number theory, an odd composite integer n is called an Euler–Jacobi pseudoprime to base a, if a and n are coprime, and

where (a/n) is the Jacobi symbol.

The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Legendre symbol article. The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are over twice as strong as tests based on Fermat's little theorem.

Every Euler–Jacobi pseudoprime is also a Fermat pseudoprime and an Euler pseudoprime. There are no numbers which are Euler–Jacobi pseudoprimes to all bases as Carmichael numbers are. 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.

These numbers are, in some sources, called Euler pseudoprimes.

The table below gives all Euler–Jacobi pseudoprimes less than 10000 for some prime bases a.

See also

Full article ▸

related documents
Landau's function
Star height problem
Elementary event
Location parameter
Simple module
Dense set
Conjugate closure
Pedal triangle
Hurwitz polynomial
De Bruijn-Newman constant
Central moment
The Third Manifesto
Online algorithm
Surjective function
Product of group subsets
Canonical Encoding Rules
Centralizer and normalizer
Euler's theorem
Group object
List of Fourier-related transforms
Context-free language
Linearity of integration
Z notation
List of basic mathematics topics