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

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$.

The prime-power contraction under pth powers is the key step. If $a=b+p^{k}h$ with $k\ge 1$, the binomial theorem givesThe first term is divisible by $p^{k+1}$. Each later term is also divisible by that power because $kj\ge k+1$ for $j\ge 2$. This includes $p=2$ and $k=1$. ThereforeStart with $x\equiv y(\mathrm{mod}{p}^n)$ and apply this implication $r$ times, increasing both the exponent and modulus at each step:The case $r=0$ is precisely the original congruence.

By Fermat's little theorem, $x^p\equiv x(\mathrm{mod}p)$. Apply the same result with initial modulus $p$ and $r=n-1$:

The finite prime-power Teichmuller representative has an explicit description. Let $y$ be the unique least nonnegative residue satisfyingRepeated Fermat's little theorem gives $y\equiv x(\mathrm{mod}p)$. Part (ii) givesso this residue has both required properties.

For uniqueness, suppose $z$ also has them. From $z^p\equiv z(\mathrm{mod}{p}^n)$, raising congruences to the $p$th power repeatedly gives $z^{p^j}\equiv z(\mathrm{mod}{p}^n)$ for every $j\ge 0$. Meanwhile $z\equiv x(\mathrm{mod}p)$ and the lifting result with $r=n-1$ implyHence $z\equiv y(\mathrm{mod}{p}^n)$. Both lie between zero and $p^n-1$, so $z=y$. Thus existence and uniqueness hold for every residue class, including zero, without needing a general Hensel lemma.