Past exam of the mathematics course of the University of Cambridge / 2014 / ia / Paper 4 / 6E / i

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.