The strategy is to construct the [group](/page/Group) of units modulo $n$, verify it is a group of order $\varphi(n)$, and apply [Element Order Divides Group Order](/theorems/783). **Step 1: Construct the group of units.** Define $G = \{a \in \{1, 2, \ldots, n-1\} : \gcd(a, n) = 1\}$ with the operation of multiplication modulo $n$. We verify $(G, \times_n)$ is a group. - *Closure:* If $\gcd(a, n) = 1$ and $\gcd(b, n) = 1$, then $\gcd(ab, n) = 1$ (since any prime dividing both $ab$ and $n$ must divide one of $a, b$ and $n$, contradicting coprimality). - *Associativity:* Inherited from multiplication of integers. - *Identity:* $1 \in G$ since $\gcd(1, n) = 1$. - *Inverses:* For $a \in G$, Bézout's theorem gives integers $x, \lambda$ with $ax - \lambda n = 1$. Reducing $x$ modulo $n$ gives an element $q \in G$ (coprime to $n$ since $aq \equiv 1 \pmod{n}$ forces $\gcd(q, n) = 1$) with $aq \equiv 1 \pmod{n}$. By definition, $|G| = \varphi(n)$. **Step 2: Apply the group-theoretic result.** For any $a \in G$, [Element Order Divides Group Order](/theorems/783) gives $a^{|G|} = a^{\varphi(n)} \equiv 1 \pmod{n}$. **Step 3: Extend to all $a$ with $\gcd(a, n) = 1$.** If $a > n - 1$, write $a = cn + d$ by the Division Algorithm with $0 \leq d < n$. Since $\gcd(a, n) = 1$, we have $\gcd(d, n) = 1$ (any common factor of $d$ and $n$ would also divide $a = cn + d$). So $d \in G$ and: \begin{align*} a^{\varphi(n)} \equiv d^{\varphi(n)} \equiv 1 \pmod{n}. \end{align*}