How to prove Euler's theorem using Lagrange's theorem?
If $a$ and $n$ are relatively prime then $a^{\phi(n)}\equiv 1 \pmod n$
Wikipedia says that it can done and that $\phi(n)$ is the order of the multiplicative group of integers modulo $n$. But I'm not sure how to proceed with the proof. Any ideas/hints?
Since $\gcd(a,n)=1$ we have that $\overline{a}\in(\mathbf{Z}/n\mathbf{Z})^*$. The order of $\overline{a}$ must divide the order of the group, which is $\phi(n)$. This gives $\overline{a}^{\phi(n)}=\overline{1}$, or in mod notation $a^{\phi(n)}=1\text{ mod }n$.