[proofplan]
We use the standard classification of finite cyclic groups up to isomorphism: every cyclic group of order $n$ is isomorphic to $(\mathbb{Z}/n\mathbb{Z}, +)$. This reduces the problem to counting generators of $\mathbb{Z}/n\mathbb{Z}$. An element $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ is a generator of the additive group if and only if $\gcd(a, n) = 1$ — this is the content of [Units in $\mathbb{Z}/n\mathbb{Z}$](/theorems/1699). Counting the residue classes with this coprimality condition yields exactly $\varphi(n)$ by definition of the Euler totient.
[/proofplan]
[step:Reduce to counting generators of $\mathbb{Z}/n\mathbb{Z}$ via the classification of cyclic groups]
Let $G$ be a cyclic group of order $n \geq 1$, and let $g_0$ be a generator. The map
\begin{align*}
\psi: \mathbb{Z}/n\mathbb{Z} &\to G \\
\bar{k} &\mapsto g_0^k
\end{align*}
is a group isomorphism: well-definedness follows from $g_0^n = e$ (so $g_0^k$ depends only on $k \bmod n$); it is a homomorphism since $\psi(\bar{k} + \bar{\ell}) = g_0^{k+\ell} = g_0^k g_0^\ell = \psi(\bar{k}) \psi(\bar{\ell})$; surjectivity holds because $g_0$ generates $G$; and injectivity follows from both sides having cardinality $n$.
Isomorphisms send generators to generators: if $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$, then $\psi(\bar{a}) = g_0^a$ generates $G$ (its powers exhaust $\psi(\mathbb{Z}/n\mathbb{Z}) = G$), and conversely if $g_0^a$ generates $G$, then $\psi^{-1}(g_0^a) = \bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$. Hence $\psi$ restricts to a bijection between the generators of $\mathbb{Z}/n\mathbb{Z}$ and the generators of $G$, and in particular
\begin{align*}
\#\{\text{generators of } G\} &= \#\{\text{generators of } \mathbb{Z}/n\mathbb{Z}\}.
\end{align*}
[guided]
The strategy is to replace the abstract group $G$ with a concrete model, $\mathbb{Z}/n\mathbb{Z}$, where generators can be described by an explicit arithmetic condition.
Let $G$ be cyclic of order $n$, and choose a generator $g_0 \in G$. Every element of $G$ has the form $g_0^k$ for some $k \in \mathbb{Z}$, and the relation $g_0^k = g_0^\ell$ holds iff $n \mid (k - \ell)$ — i.e., iff $k \equiv \ell \pmod n$. This suggests defining
\begin{align*}
\psi: \mathbb{Z}/n\mathbb{Z} &\to G \\
\bar{k} &\mapsto g_0^k.
\end{align*}
We verify the required properties of $\psi$:
\begin{itemize}
\item \textbf{Well-defined.} If $\bar{k} = \bar{\ell}$, then $n \mid (k - \ell)$. Since $g_0^n = e$, we have $g_0^{k} = g_0^{k - \ell} g_0^\ell = (g_0^n)^{(k-\ell)/n} g_0^\ell = g_0^\ell$, so $\psi(\bar{k}) = \psi(\bar{\ell})$.
\item \textbf{Homomorphism.} $\psi(\bar{k} + \bar{\ell}) = \psi(\overline{k + \ell}) = g_0^{k+\ell} = g_0^k g_0^\ell = \psi(\bar{k})\psi(\bar{\ell})$.
\item \textbf{Surjective.} Every element of $G$ is $g_0^k$ for some $k$, since $g_0$ generates $G$.
\item \textbf{Injective.} Both domain and codomain have exactly $n$ elements (the codomain because $|G| = n$), so a surjection is automatically a bijection.
\end{itemize}
Hence $\psi$ is a group isomorphism.
Under an isomorphism, generators correspond to generators: if $\bar{a}$ generates $\mathbb{Z}/n\mathbb{Z}$, then its image $\psi(\bar{a}) = g_0^a$ generates $G$, since $\psi$ maps the cyclic subgroup $\langle \bar{a} \rangle = \mathbb{Z}/n\mathbb{Z}$ onto $\psi(\mathbb{Z}/n\mathbb{Z}) = G$; the same argument with $\psi^{-1}$ handles the converse. We therefore have a bijection between generators of the two groups, and
\begin{align*}
\#\{\text{generators of } G\} &= \#\{\text{generators of } \mathbb{Z}/n\mathbb{Z}\}.
\end{align*}
[/guided]
[/step]
[step:Identify generators of $\mathbb{Z}/n\mathbb{Z}$ with residue classes coprime to $n$]
By [Units in $\mathbb{Z}/n\mathbb{Z}$](/theorems/1699), for any $a \in \mathbb{Z}$ the residue class $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ is a generator of the additive group $(\mathbb{Z}/n\mathbb{Z}, +)$ if and only if $\gcd(a, n) = 1$. Consequently
\begin{align*}
\#\{\text{generators of } \mathbb{Z}/n\mathbb{Z}\} &= \#\bigl\{\bar{a} \in \mathbb{Z}/n\mathbb{Z} : \gcd(a, n) = 1\bigr\}.
\end{align*}
Note that the coprimality condition $\gcd(a, n) = 1$ depends only on $\bar{a}$ — if $a \equiv a' \pmod n$, then $\gcd(a, n) = \gcd(a', n)$ because integer linear combinations with $n$ preserve the gcd — so the right-hand cardinality is well-defined.
[/step]
[step:Evaluate the count as $\varphi(n)$ by definition of the Euler totient]
Choose the standard representatives $\{0, 1, 2, \dots, n-1\}$ for the residue classes in $\mathbb{Z}/n\mathbb{Z}$. The bijection $a \leftrightarrow \bar{a}$ between this set and $\mathbb{Z}/n\mathbb{Z}$ restricts to a bijection between
\begin{align*}
\{a \in \{0, 1, \dots, n-1\} : \gcd(a, n) = 1\} \quad \text{and} \quad \{\bar{a} \in \mathbb{Z}/n\mathbb{Z} : \gcd(a, n) = 1\}.
\end{align*}
The Euler totient $\varphi(n)$ is defined as the cardinality of the left-hand set — equivalently, the number of integers in $\{1, 2, \dots, n\}$ coprime to $n$, the same count since $\gcd(0, n) = n \neq 1$ for $n \geq 2$ (and for $n = 1$ both sides equal $1$). Combining with Step 2,
\begin{align*}
\#\{\text{generators of } \mathbb{Z}/n\mathbb{Z}\} &= \varphi(n).
\end{align*}
Combining with Step 1,
\begin{align*}
\#\{\text{generators of } G\} &= \varphi(n),
\end{align*}
completing the proof.
[/step]
