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}\equiv 1(\mathrm{mod}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^{k}m$ with $k\ge 2$ and $\gcd (p,m)=1$, the Chinese remainder theorem supplies $a\equiv 1+p(\mathrm{mod}{p}^k)$ and $a\equiv 1(\mathrm{mod}m)$. This $a$ is coprime to $N$. But the binomial theorem givescontradicting 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(\mathrm{mod}p)$ and $a\equiv 1(\mathrm{mod}N/p)$. The Chinese remainder theorem applies because $N$ is squarefree. The Carmichael congruence implies $g^{N-1}\equiv 1(\mathrm{mod}p)$. Since $g$ has multiplicative order $p-1$, that order divides $N-1$. This proves the other condition.^[ref]