**Solution to Abstract Algebra by Dummit & Foote 3rd edition Chapter 3.2 Exercise 3.2.22**

Use Lagrange’s Theorem in the multiplicative group $G = (\mathbb{Z}/(n))^\times$ to prove Euler’s Theorem: if $\mathsf{gcd}(a,n) = 1$ then $a^{\varphi(n)} \equiv 1 \pmod n$. ($\varphi$ denotes the Euler totient function.)

Solution: If $\mathsf{gcd}(a,n) = 1$, then $\overline{a} \in \mathbb{Z}/(n)^\times$. By Lagrange’s Theorem, $|a|$ divides $|G| = \varphi(n)$. Thus $$a^{\varphi(n)} \equiv 1 \pmod n.$$