Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 4 / 11G / a

The Fermat-Euler theorem states thatIndeed, if $r_1,\dots ,r_{\phi (n)}$ are the reduced residue classes modulo $n$, multiplication by $a$ permutes them. ThereforeThe product ${\prod }_i{r}_i$ is invertible modulo $n$, so cancellation gives the theorem.

Now let $p$ be prime. If $k\equiv 1(\mathrm{mod}p-1)$, then for $p\nmid b$, Fermat little theorem gives $b^{k-1}\equiv 1(\mathrm{mod}p)$, while $p\mid b$ makes $b^k\equiv b\equiv 0$. Thus $b^k\equiv b$ for every integer $b$.

Conversely, assume this congruence holds for every $b$. Choose a primitive root $g$ modulo $p$. Then $g^{k-1}\equiv 1(\mathrm{mod}p)$. Since $g$ has order $p-1$, one has $p-1\mid k-1$. Hence