= Proof of Korselt criterion
For sufficiency, let $N$ be composite and squarefree, with $p-1\mid N-1$ for every <prime factor> $p$. For any <integer> $a$ <coprime> to $N$, <Fermat's little theorem> gives $a^{N-1}\equiv1\pmod p$ for every such $p$. Their product is $N$, so the <Chinese remainder theorem> gives the required congruence modulo $N$.
For necessity, first rule out a repeated factor. If $N=p^km$ with $k\ge2$ and $\gcd(p,m)=1$, the <Chinese remainder theorem> supplies $a\equiv1+p\pmod{p^k}$ and $a\equiv1\pmod m$. This $a$ is <coprime> to $N$. But the <binomial theorem> gives
$$
a^{N-1}\equiv(1+p)^{N-1}\equiv1+(N-1)p\equiv1-p\not\equiv1\pmod{p^2},
$$
contradicting the <Carmichael number> condition. Hence $N$ is squarefree.
Now choose a <primitive root> $g$ modulo a <prime factor> $p$. Lift it to a <unit> modulo $N$ by prescribing $a\equiv g\pmod p$ and $a\equiv1\pmod{N/p}$. The <Chinese remainder theorem> applies because $N$ is squarefree. The Carmichael congruence implies $g^{N-1}\equiv1\pmod p$. Since $g$ has <multiplicative order> $p-1$, that order divides $N-1$. This proves the other condition.<Carmichael Numbers and Korselt's Criterion by Keith Conrad>[Theorem 2 proof, printed p. 2: repeated prime factors, primitive roots and Chinese remainder lifting]{ref}
Back to article page
