= Euler witness
{c}
For an <odd integer> $N>1$ and a base $b$ <coprime> to $N$, an <Euler witness> is a base for which
$$
b^{(N-1)/2}\not\equiv\left(\frac bN\right)\pmod N.
$$
By <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\equiv8\pmod{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.
Back to article page
