= Solution
For <Fermat's little theorem>, first suppose $p\nmid x$. Multiplication by $x$ permutes the nonzero residue classes modulo $p$: if $xa\equiv xb\pmod p$, the prime cannot divide $x$, so cancellation gives $a\equiv b\pmod p$. Multiplying the representatives in this permutation,
$$
x^{p-1}(p-1)!\equiv(p-1)!\pmod p.
$$
Every factor of the factorial is nonzero modulo the prime, so the factorial has a <modular inverse> and can be cancelled. Thus $x^{p-1}\equiv1\pmod p$ and $x^p\equiv x\pmod p$. If $p\mid x$, both sides are zero modulo $p$. Hence for every integer $x$,
$$
\boxed{x^p\equiv x\pmod p.}
$$
For completeness, the cancellation used above follows from <Bézout's identity>: a number relatively prime to $p$ has an inverse modulo $p$.
Back to article page
