Euler–Jacobi pseudoprime

In number theory, an odd integer n is called an Euler–Jacobi probable prime (or, more commonly, an Euler probable prime) to base a, if a and n are coprime, and

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right){\pmod {n}}$

where $\left({\frac {a}{n}}\right)$ is the Jacobi symbol. The Jacobi symbol evaluates to 0 if a and n are not coprime, so the test can alternatively be expressed as:

$a^{(n-1)/2}\equiv \left({\frac {a}{n}}\right)\neq 0{\pmod {n}}.$

If n is an odd composite integer that satisfies the above congruence, then n is called an Euler–Jacobi pseudoprime (or, more commonly, an Euler pseudoprime) to base a.

As long as a is not a multiple of n (usually 2 ≤ a < n), then if a and n are not coprime, n is definitely composite, as 1 < gcd(a,n) < n is a factor of n.

Properties

The motivation for this definition is the fact that all prime numbers n satisfy the above equation, as explained in the Euler's criterion 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.

The smallest Euler–Jacobi pseudoprime base 2 is 561. There are 11347 Euler–Jacobi pseudoprimes base 2 that are less than 25·10⁹ (see OEIS: A047713) (page 1005 of ).

In the literature (for example,), an Euler–Jacobi pseudoprime as defined above is often called simply an Euler pseudoprime.

Implementation in Lua

function EulerJacobiTest(k)
        a = 2
        if k == 1 then return false
        elseif k == 2 then return true
        else
                if(modPow(a,(k-1)/2,k) == Jacobi(a,k)) then
                        return true
                else
                        return false
                end
        end
end

See also

• Probable prime