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