= Existence of an Euler witness for every odd composite integer
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^eM$ with $e\geq2$ and $p\nmid M$. The <Chinese remainder theorem> chooses $b\equiv1+p\pmod{p^e}$ and $b\equiv1\pmod 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\equiv1+hp\pmod{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$.
Back to article page
