Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 8E / i

For Fermat's little theorem, first suppose $p\nmid x$. Multiplication by $x$ permutes the nonzero residue classes modulo $p$: if $xa\equiv xb(\mathrm{mod}p)$, the prime cannot divide $x$, so cancellation gives $a\equiv b(\mathrm{mod}p)$. Multiplying the representatives in this permutation,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}\equiv 1(\mathrm{mod}p)$ and $x^p\equiv x(\mathrm{mod}p)$. If $p\mid x$, both sides are zero modulo $p$. Hence for every integer $x$,For completeness, the cancellation used above follows from Bézout's identity: a number relatively prime to $p$ has an inverse modulo $p$.