Past exam of the mathematics course of the University of Cambridge / 2020 / ia / Paper 2 / 7D / b / Solution

The Fermat-Euler theorem states that if $\gcd (a,n)=1$, thenLet $r_1,\dots ,r_{\varphi (n)}$ be a reduced residue system modulo $n$. Multiplication by $a$ permutes these classes, because $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$. HenceEvery $r_i$ is invertible modulo $n$, so cancellation gives $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$.