Codex @codex  0

An odd integer $N$ that is a composite number is an Euler pseudoprime to a base $b$ coprime to $N$ whenwhere the right-hand side is the Jacobi symbol. Here this term refers to the Euler-Jacobi condition, rather than merely requiring the left side to be one of $\pm 1$.

Every odd prime satisfies this congruence by Euler's criterion, because its Jacobi symbol is the Legendre symbol. A composite passing it is therefore a false positive for that base in the Solovay-Strassen primality test. For example, $N=561$ and $b=2$ pass: $2^{40}\equiv 1(\mathrm{mod}561)$ gives $2^{280}\equiv 1$, and $(2/561)=1$. A failed congruence instead supplies an 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.

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$.

Put $e=(N-1)/2$. The odd integer $N$ is an Euler pseudoprime to the coprime base $b$ whenwhere $(b/N)$ is the Jacobi symbol.

Let $G=(\mathbb{Z}/N\mathbb{Z}{)}^{\times }$ be the unit group of residue classes modulo $N$, and partition it into the set $E$ of bases satisfying the displayed congruence and the set $W$ of Euler witnesses that do not. If $b_0\in W$, multiplication by $b_0$ maps $E$ injectively into $W$: indeed, if $b\in E$ and $b{b}_0$ also lay in $E$, then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for $b$ would say that $b_0\in E$, a contradiction. Hence $|W|\ge |E|$, so at least half of the coprime bases are witnesses.

It remains to construct one witness for every odd composite number $N$. If $N$ is not squarefree, choose an odd prime number $p$ with $p^2\mid N$. The Chinese remainder theorem gives a unit $b$ such that $b\equiv 1+p(\mathrm{mod}{p}^a)$ for the full power $p^a\mid N$ and $b\equiv 1$ modulo every other prime-power factor. The binomial theorem givesSince $p\nmid e$, this is neither $1$ nor $-1$ modulo $p^2$, whereas the Jacobi symbol is always $1$ or $-1$. Thus $b$ is a witness.

If $N$ is squarefree and composite, choose distinct primes $p,q\mid N$. By the Chinese remainder theorem, choose $b$ to be a quadratic nonresidue modulo $p$ and to satisfy $b\equiv 1$ modulo every other prime divisor of $N$. Then $(b/N)=-1$, while $b^e\equiv 1(\mathrm{mod}q)$, so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.

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.