Euler witness

For an odd integer $N$ and a unit $b$ modulo $N$, the base $b$ is an Euler witness whenIt therefore certifies that $N$ is composite.

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 odd composite integer has an Euler witness. For a nonsquarefree integer, a base congruent to $1+p$ modulo a repeated prime factor $p^2$ fails the Euler congruence by the binomial theorem. For a squarefree integer, use the Chinese remainder theorem to choose a base that is a quadratic nonresidue modulo one prime factor and $1$ modulo another. Its Jacobi symbol is $-1$, while its power is $1$ modulo the second factor.

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.