Past exam of the mathematics course of the University of Cambridge / 2004 / ia / Paper 4 / 6E (Numbers and Sets)

For a prime number $p$ and an integer $x$ coprime to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx(\mathrm{mod}p)$ implies $a\equiv b(\mathrm{mod}p)$, and none of the products is zero. Taking the product over the $p-1$ classes givesThe factorial is coprime to $p$ and can be cancelled, proving Fermat little theorem: $\boxed{x^{p-1}\equiv 1(\mathrm{mod}p)}$.

Now $n=mp$ and $x$ is coprime to $n$, so it is coprime to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem givesThus the two specified integer congruences modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.

If $n$ is a squarefree integer, its distinct prime factors are pairwise coprime. Consequently $n$ divides $x^{n-1}-1$ exactly when every prime factor does. Applying the preceding equivalence with $m=n/p$ provesFinally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. Fermat little theorem gives $x^{n-1}=(x^{p-1}{)}^{k_p}\equiv 1(\mathrm{mod}p)$ for every prime factor. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv 1(\mathrm{mod}n)}$. For composite $n$ this is the sufficient direction of the Korselt criterion for a Carmichael number; primality is not excluded by the requested implication.