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