Proof of Korselt criterion
= Proof of Korselt criterion
If every integer satisfies $a^n\equiv a\pmod n$, taking $a=p$ shows that $p^2$ cannot divide $n$. Taking a <primitive root> modulo each prime divisor $p$ shows $p-1\mid n-1$. Conversely, these divisibilities and squarefreeness let <Fermat's little theorem> prove the congruence modulo each prime divisor, and coprimality of those divisors combines it modulo $n$.