[proofplan]
We work in the [reduced residue classes](/page/modular%20arithmetic) modulo $m$. The hypothesis $\gcd(a,m)=1$ makes multiplication by $a$ an invertible operation on these classes, so it permutes the $\varphi(m)$ units modulo $m$. Comparing the product of all reduced residues before and after this permutation gives a congruence with a cancellable unit factor, and cancellation yields $a^{\varphi(m)} \equiv 1 \pmod m$.
[/proofplan]
[step:List the reduced residue classes modulo $m$]
Let $[x]_m$ denote the residue class of an integer $x \in \mathbb{Z}$ in $\mathbb{Z}/m\mathbb{Z}$. Define the reduced residue set
\begin{align*}
U := \{u \in \{1,\dots,m\} : \gcd(u,m)=1\}.
\end{align*}
By the definition of the [Euler totient function](/page/Euler%20totient%20function) in the theorem statement, $|U|=\varphi(m)$. Choose an enumeration
\begin{align*}
U=\{u_1,\dots,u_{\varphi(m)}\}.
\end{align*}
The residue classes $[u_1]_m,\dots,[u_{\varphi(m)}]_m$ are pairwise distinct because each $u_i$ lies in $\{1,\dots,m\}$.
[/step]
[step:Show that multiplication by $a$ permutes the reduced residue classes]
Since $\gcd(a,m)=1$, Bezout's Identity gives integers $b,c \in \mathbb{Z}$ such that
\begin{align*}
ab+mc=1.
\end{align*}
Hence $[a]_m[b]_m=[1]_m$, so $[a]_m$ is a unit in $\mathbb{Z}/m\mathbb{Z}$.
[claim:Multiplication by $a$ permutes reduced residues]
The residue classes $[au_1]_m,\dots,[au_{\varphi(m)}]_m$ are exactly the residue classes $[u_1]_m,\dots,[u_{\varphi(m)}]_m$ in some order.
[/claim]
[proof]
For each index $i \in \{1,\dots,\varphi(m)\}$, the class $[u_i]_m$ is a unit because $\gcd(u_i,m)=1$, again by Bezout's Identity. Since the product of two units is a unit, $[a u_i]_m=[a]_m[u_i]_m$ is a unit.
The classes $[a u_i]_m$ are pairwise distinct. Indeed, if $[a u_i]_m=[a u_j]_m$, then multiplying both sides by the inverse $[b]_m$ of $[a]_m$ gives
\begin{align*}
[u_i]_m=[b]_m[a u_i]_m=[b]_m[a u_j]_m=[u_j]_m.
\end{align*}
Since $u_i,u_j \in \{1,\dots,m\}$ are chosen as distinct representatives, $[u_i]_m=[u_j]_m$ implies $u_i=u_j$.
Thus $[au_1]_m,\dots,[au_{\varphi(m)}]_m$ are $\varphi(m)$ distinct unit classes. There are exactly $\varphi(m)$ unit classes represented by $U$, so these classes are precisely $[u_1]_m,\dots,[u_{\varphi(m)}]_m$ in some order.
[/proof]
[guided]
We first prove that multiplying by $a$ is reversible modulo $m$. The hypothesis $\gcd(a,m)=1$ is exactly what is needed: by Bezout's Identity, there exist integers $b,c \in \mathbb{Z}$ satisfying
\begin{align*}
ab+mc=1.
\end{align*}
Reducing this identity modulo $m$ gives
\begin{align*}
[a]_m[b]_m=[1]_m,
\end{align*}
so $[b]_m$ is the inverse of $[a]_m$ in $\mathbb{Z}/m\mathbb{Z}$.
Now fix an index $i \in \{1,\dots,\varphi(m)\}$. Since $u_i \in U$, we have $\gcd(u_i,m)=1$, so the same Bezout argument shows that $[u_i]_m$ is a unit. Therefore
\begin{align*}
[au_i]_m=[a]_m[u_i]_m
\end{align*}
is a product of units, hence is again a unit.
It remains to show that no two of the classes $[au_i]_m$ coincide. Suppose $[au_i]_m=[au_j]_m$. Because $[b]_m$ is the inverse of $[a]_m$, multiplication by $[b]_m$ cancels the factor $[a]_m$:
\begin{align*}
[u_i]_m=[b]_m[au_i]_m=[b]_m[au_j]_m=[u_j]_m.
\end{align*}
The integers $u_i$ and $u_j$ both lie in the complete representative range $\{1,\dots,m\}$, so equality of their residue classes forces $u_i=u_j$. Hence the classes $[au_i]_m$ are pairwise distinct.
We have found $\varphi(m)$ distinct unit classes modulo $m$. Since $U$ contains exactly $\varphi(m)$ representatives of the unit classes by definition of $\varphi(m)$, the list $[au_1]_m,\dots,[au_{\varphi(m)}]_m$ must be the same list as $[u_1]_m,\dots,[u_{\varphi(m)}]_m$, only reordered.
[/guided]
[/step]
[step:Compare the products before and after the permutation]
Because multiplication by $a$ permutes the reduced residue classes, the products of the two lists are equal in $\mathbb{Z}/m\mathbb{Z}$:
\begin{align*}
[au_1]_m[au_2]_m\cdots[au_{\varphi(m)}]_m
=
[u_1]_m[u_2]_m\cdots[u_{\varphi(m)}]_m.
\end{align*}
Using associativity and commutativity of multiplication in $\mathbb{Z}/m\mathbb{Z}$, the left-hand side factors as
\begin{align*}
[au_1]_m[au_2]_m\cdots[au_{\varphi(m)}]_m
=
[a]_m^{\varphi(m)}[u_1]_m[u_2]_m\cdots[u_{\varphi(m)}]_m.
\end{align*}
Therefore
\begin{align*}
[a]_m^{\varphi(m)}[u_1]_m[u_2]_m\cdots[u_{\varphi(m)}]_m
=
[u_1]_m[u_2]_m\cdots[u_{\varphi(m)}]_m.
\end{align*}
[/step]
[step:Cancel the product of the reduced residues]
Define the residue class
\begin{align*}
z := [u_1]_m[u_2]_m\cdots[u_{\varphi(m)}]_m \in \mathbb{Z}/m\mathbb{Z}.
\end{align*}
Each factor $[u_i]_m$ is a unit, so $z$ is a unit. Multiplying
\begin{align*}
[a]_m^{\varphi(m)}z=z
\end{align*}
by $z^{-1}$ gives
\begin{align*}
[a]_m^{\varphi(m)}=[1]_m.
\end{align*}
By the definition of congruence modulo $m$, this is exactly
\begin{align*}
a^{\varphi(m)} \equiv 1 \pmod m.
\end{align*}
[/step]
