Solution
= Solution
The <Fermat-Euler theorem> states that if $\gcd(a,n)=1$, then
$$
\boxed{a^{\phi(n)}\equiv1\pmod n}.
$$
Let $r_1,\ldots,r_{\phi(n)}$ be a reduced residue system modulo $n$. Multiplication by $a$ permutes these classes, because $ar_i\equiv ar_j\pmod n$ implies $r_i\equiv r_j\pmod n$. Hence
$$
\prod_i ar_i\equiv\prod_i r_i\pmod n.
$$
Every $r_i$ is invertible modulo $n$, so cancellation gives $a^{\phi(n)}\equiv1\pmod n$.