= Solution
\b[True.] First suppose $p^e\mid N$ with $e\geq2$ maximal. By the <Chinese remainder theorem>, choose $a\equiv1+p^{e-1}\pmod{p^e}$ and $a\equiv1$ modulo all other prime-power factors. This is a unit, with <Jacobi symbol> one, because it is one modulo every prime. For $m=(N-1)/2$, the <binomial theorem> gives
$$
a^m\equiv1+mp^{e-1}\not\equiv1\pmod{p^e},
$$
because $p\nmid m$ and all higher terms contain $p^e$. It is therefore a witness to the desired failure.
If $N$ is square-free and composite, it has at least two prime factors. Choose $a$ to be a <quadratic nonresidue> at one prime $p$ and one at every other prime, again using the <Chinese remainder theorem>. Then $(a/N)=-1$. At a different odd prime $q\mid N$, however, $a^m\equiv1\not\equiv-1\pmod q$. These two cases prove that \b[every odd composite has an Euler-Jacobi witness], unlike the situation for the ordinary <Fermat primality test>.
Back to article page
