Euler witness

For an odd integer $N>1$ and a base $b$ coprime to $N$, an Euler witness is a base for whichBy Euler's criterion, this failure cannot occur for an odd prime, so it certifies that $N$ is a composite number.

For example, take $N=15$ and $b=2$. Then $2^7\equiv 8(\mathrm{mod}15)$, while the Jacobi symbol is $(2/15)=(2/3)(2/5)=(-1)(-1)=1$. Thus the base two witnesses the compositeness of fifteen without supplying its factors. If instead $1<\gcd (b,N)<N$, the greatest common divisor already gives a proper divisor, so a primality test can reject before computing this congruence.

If one Euler witness $b_0$ exists modulo $N$, multiplication by $b_0$ injects the set of nonwitnesses into the set of witnesses. Indeed, the product of $b_0$ with a nonwitness cannot be another nonwitness, because cancellation and multiplicativity of the Jacobi symbol would make $b_0$ a nonwitness. Thus at least half of the units modulo $N$ are Euler witnesses.

Every composite number $N$ that is an odd integer has an Euler witness. There are two cases.

If $p^2$ divides $N$ for a prime number $p$, write $N=p^{e}M$ with $e\ge 2$ and $p\nmid M$. The Chinese remainder theorem chooses $b\equiv 1+p(\mathrm{mod}{p}^e)$ and $b\equiv 1(\mathrm{mod}M)$. This base is a unit modulo $N$ and has Jacobi symbol $(b/N)=1$, because it is one modulo every prime divisor. But with $h=(N-1)/2$, the binomial theorem gives $b^h\equiv 1+hp(\mathrm{mod}{p}^2)$. Since $p\nmid h$, this is not one, so the Euler congruence fails.

If $N$ is squarefree, it has at least two distinct prime factors. Choose $b$ to be a quadratic nonresidue modulo one factor and one modulo every other factor, again by the Chinese remainder theorem. Then $(b/N)=-1$, while $b^{(N-1)/2}$ is one modulo a different prime factor. It therefore cannot equal the Jacobi symbol modulo $N$.

The Solovay-Strassen primality test samples unit bases and rejects an odd candidate as composite when it finds an Euler witness. Every prime passes every base by Euler's criterion, while an odd composite passes a random base with probability at most one half.