Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 1G / Solution

A Carmichael number is a composite $N$ such that $a^{N-1}\equiv 1(\mathrm{mod}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.