= Solution
A <Carmichael number> is a composite $N$ such that $a^{N-1}\equiv1\pmod N$ for every $a$ coprime to $N$. For $p\mid N$, choose by CRT a number whose residue mod $p$ is a primitive root; its order $p-1$ divides $N-1$. If $p^2\mid N$, choose instead a primitive root modulo $p^2$; then $p(p-1)\mid N-1$, impossible because $p\mid N$. Thus $N$ is square-free. Write $N=pm$. Since $p-1\mid N-1$, also $p-1\mid m-1$; compositeness gives $m>1$, hence $m\ge p$ and $p\le\sqrt N$. This is <Korselt criterion>.
Back to article page
