[proofplan]
We pass from the integer $a$ to its residue class $\bar{a}$ in the quotient ring $\mathbb{Z}/n\mathbb{Z}$. Since $\gcd(a,n)=1$, this residue class is a unit, and the unit group has exactly $\varphi(n)$ elements by the reduced-residue-class description of units modulo $n$. Multiplication by the unit $\bar{a}$ permutes the finite unit group, so multiplying all elements before and after this permutation gives $\bar{a}^{\varphi(n)}=1$ in $\mathbb{Z}/n\mathbb{Z}$. Translating equality of residue classes back to congruence gives the desired result.
[/proofplan]
[step:Identify $a$ as a unit modulo $n$ and enumerate the unit group]
Let
\begin{align*}
R := \mathbb{Z}/n\mathbb{Z}
\end{align*}
be the quotient ring, and let
\begin{align*}
\pi: \mathbb{Z} \to R
\end{align*}
be the quotient map defined by $\pi(x)=x+n\mathbb{Z}$. Write $\bar{a}:=\pi(a)$.
Since $\gcd(a,n)=1$, [citetheorem:7884] gives $\bar{a}\in R^\times$. The same theorem gives
\begin{align*}
|R^\times|=\varphi(n).
\end{align*}
Set
\begin{align*}
m:=\varphi(n).
\end{align*}
Since $R^\times$ is a finite set with $m$ elements, choose an enumeration
\begin{align*}
R^\times=\{u_1,\dots,u_m\}.
\end{align*}
[/step]
[step:Show that multiplication by $\bar{a}$ permutes the units]
Define the map
\begin{align*}
M_{\bar{a}}: R^\times &\to R^\times
\end{align*}
by
\begin{align*}
M_{\bar{a}}(u):=\bar{a}u.
\end{align*}
This map is well-defined because the product of two units in a ring is again a unit. Since $\bar{a}\in R^\times$, let $\bar{a}^{-1}\in R^\times$ denote its inverse. Define
\begin{align*}
M_{\bar{a}^{-1}}: R^\times &\to R^\times
\end{align*}
by
\begin{align*}
M_{\bar{a}^{-1}}(u):=\bar{a}^{-1}u.
\end{align*}
For every $u\in R^\times$,
\begin{align*}
M_{\bar{a}^{-1}}(M_{\bar{a}}(u))=\bar{a}^{-1}\bar{a}u=u.
\end{align*}
Also,
\begin{align*}
M_{\bar{a}}(M_{\bar{a}^{-1}}(u))=\bar{a}\bar{a}^{-1}u=u.
\end{align*}
Thus $M_{\bar{a}}$ is a bijection of $R^\times$.
[guided]
The point of this step is to make precise the phrase “multiplication by $a$ permutes the reduced residue classes.” We work inside the unit group $R^\times$, where $R=\mathbb{Z}/n\mathbb{Z}$, because [citetheorem:7884] has already converted the condition $\gcd(a,n)=1$ into the statement that $\bar{a}$ is invertible.
Define
\begin{align*}
M_{\bar{a}}: R^\times &\to R^\times
\end{align*}
by
\begin{align*}
M_{\bar{a}}(u):=\bar{a}u.
\end{align*}
This is a map from $R^\times$ to itself: if $u\in R^\times$, then both $\bar{a}$ and $u$ have multiplicative inverses in $R$, so their product $\bar{a}u$ also has a multiplicative inverse, namely $u^{-1}\bar{a}^{-1}$.
To prove that $M_{\bar{a}}$ is a permutation, it is enough to construct its inverse. Since $\bar{a}$ is a unit, there exists $\bar{a}^{-1}\in R^\times$ satisfying $\bar{a}^{-1}\bar{a}=1$ and $\bar{a}\bar{a}^{-1}=1$. Define
\begin{align*}
M_{\bar{a}^{-1}}: R^\times &\to R^\times
\end{align*}
by
\begin{align*}
M_{\bar{a}^{-1}}(u):=\bar{a}^{-1}u.
\end{align*}
Then, for every $u\in R^\times$,
\begin{align*}
M_{\bar{a}^{-1}}(M_{\bar{a}}(u))=\bar{a}^{-1}(\bar{a}u)=(\bar{a}^{-1}\bar{a})u=u.
\end{align*}
Similarly,
\begin{align*}
M_{\bar{a}}(M_{\bar{a}^{-1}}(u))=\bar{a}(\bar{a}^{-1}u)=(\bar{a}\bar{a}^{-1})u=u.
\end{align*}
Therefore $M_{\bar{a}^{-1}}$ is a two-sided inverse for $M_{\bar{a}}$, and $M_{\bar{a}}$ is a bijection of $R^\times$.
[/guided]
[/step]
[step:Multiply the permuted unit classes and cancel their product]
Because $M_{\bar{a}}$ is a bijection of $R^\times$, the list
\begin{align*}
\bar{a}u_1,\dots,\bar{a}u_m
\end{align*}
is another enumeration of the same finite set $R^\times$. Hence the products of the two enumerations are equal in the commutative ring $R$:
\begin{align*}
(\bar{a}u_1)\cdots(\bar{a}u_m)=u_1\cdots u_m.
\end{align*}
By associativity and commutativity of multiplication in $R$,
\begin{align*}
\bar{a}^{m}(u_1\cdots u_m)=u_1\cdots u_m.
\end{align*}
Define
\begin{align*}
U:=u_1\cdots u_m\in R.
\end{align*}
Since each $u_i$ is a unit, $U$ is a unit. Multiplying both sides of the preceding equality by $U^{-1}$ gives
\begin{align*}
\bar{a}^{m}=1.
\end{align*}
Since $m=\varphi(n)$, this is
\begin{align*}
\bar{a}^{\varphi(n)}=1
\end{align*}
in $\mathbb{Z}/n\mathbb{Z}$.
[/step]
[step:Translate equality in the quotient ring back to congruence modulo $n$]
The equality
\begin{align*}
\bar{a}^{\varphi(n)}=1
\end{align*}
in $\mathbb{Z}/n\mathbb{Z}$ means
\begin{align*}
a^{\varphi(n)}+n\mathbb{Z}=1+n\mathbb{Z}.
\end{align*}
By the definition of residue classes modulo $n$, this is equivalent to
\begin{align*}
n \mid \left(a^{\varphi(n)}-1\right).
\end{align*}
Therefore
\begin{align*}
a^{\varphi(n)} \equiv 1 \pmod{n}.
\end{align*}
This proves Euler's theorem for every positive modulus $n$.
[/step]
