Structure and Classification of Cyclic Groups

We use the First Isomorphism Theorem framework by explicitly constructing and analyzing the natural surjective homomorphism from $\mathbb{Z}$ onto $G$; this is a direct construction, not a use of any theorem built on top of the present classification, so there is no circularity.

Step 1: A surjective homomorphism $\phi: \mathbb{Z} \to G$. Define $\phi: \mathbb{Z} \to G$ by $\phi(k) = g^k$. This is well-defined for every integer $k$ since $G$ is a group (inverses and all powers exist). It is a homomorphism because

for all $k, l \in \mathbb{Z}$, using only the group axioms (associativity and the laws of exponents, which follow from associativity by induction). It is surjective because $G = \langle g \rangle$ means every element of $G$ is exactly $g^k$ for some $k \in \mathbb{Z}$, i.e. every element of $G$ lies in the image of $\phi$.

Step 2: The kernel of $\phi$ is a subgroup of $\mathbb{Z}$, hence of the form $n\mathbb{Z}$. Let $K = \ker \phi = \{ k \in \mathbb{Z} : g^k = e \}$. Since $\phi$ is a homomorphism, $K$ is a subgroup of $\mathbb{Z}$ (kernels of homomorphisms are always subgroups: $\phi(0)=e$ so $0 \in K$; if $k,l \in K$ then $\phi(k-l) = \phi(k)\phi(l)^{-1} = e$ so $k - l \in K$). We claim every subgroup of $\mathbb{Z}$ has the form $n\mathbb{Z}$ for some integer $n \geq 0$. If $K = \{0\}$, take $n = 0$. Otherwise $K$ contains a nonzero integer, and since $K$ is closed under negation it contains a positive integer; let $n$ be the least positive element of $K$ (this exists by the well-ordering principle). We show $K = n\mathbb{Z}$.

• $n\mathbb{Z} \subseteq K$: since $n \in K$ and $K$ is closed under addition and negation, all integer multiples of $n$ lie in $K$.
• $K \subseteq n\mathbb{Z}$: let $k \in K$. By the division algorithm, $k = qn + r$ with $0 \leq r < n$. Then $r = k - qn \in K$ since $k \in K$, $n \in K$, and $K$ is a subgroup (closed under subtraction and integer combinations). Since $n$ was the least positive element of $K$ and $0 \le r < n$, we must have $r = 0$. Hence $k = qn \in n\mathbb{Z}$.

So $K = n\mathbb{Z}$ for a unique $n \geq 0$.

Step 3: Interpreting $n$. Case $n = 0$: Then $K = \{0\}$, so $\phi$ is injective (its kernel is trivial: if $\phi(k) = \phi(l)$ then $\phi(k - l) = e$ so $k - l \in K = \{0\}$, i.e. $k = l$). An injective surjective homomorphism is an isomorphism, so $\phi: \mathbb{Z} \to G$ is an isomorphism and $G \cong \mathbb{Z}$. Note $K = \{0\}$ means no positive integer $k$ satisfies $g^k = e$, i.e. $g$ has infinite order — matching case (1) of the theorem. Case $n > 0$: Then $g^n = e$ and $n$ is the least positive integer with this property (by minimality of $n$ as the least positive element of $K$), so $g$ has order exactly $n$ — matching case (2). We now build an explicit isomorphism $\overline{\phi}: \mathbb{Z}/n\mathbb{Z} \to G$. Define $\overline{\phi}(\bar k) = g^k$ for $\bar k \in \mathbb{Z}/n\mathbb{Z}$.

• Well-defined: if $\bar k = \bar l$ in $\mathbb{Z}/n\mathbb{Z}$, then $k - l \in n\mathbb{Z} = K = \ker\phi$, so $\phi(k) = \phi(l)$, i.e. $g^k = g^l$. So the value $\overline\phi(\bar k)$ does not depend on the choice of representative $k$.
• Homomorphism: $\overline\phi(\bar k + \bar l) = \overline\phi(\overline{k+l}) = g^{k+l} = g^k g^l = \overline\phi(\bar k)\overline\phi(\bar l)$.
• Surjective: for any $x \in G$, since $G = \langle g\rangle$, $x = g^k = \overline\phi(\bar k)$ for some $k$.
• Injective: if $\overline\phi(\bar k) = \overline\phi(\bar l)$ then $g^{k - l} = e$, so $k - l \in K = n\mathbb{Z}$, so $\bar k = \bar l$ in $\mathbb{Z}/n\mathbb{Z}$.

So $\overline\phi$ is an isomorphism, giving $G \cong \mathbb{Z}/n\mathbb{Z}$. Since $\mathbb{Z}/n\mathbb{Z}$ has exactly the $n$ elements $\bar 0, \bar 1, \dots, \overline{n-1}$, we get $|G| = n$.

Step 4: Same order $\Rightarrow$ isomorphic; different order $\Rightarrow$ not isomorphic. By Steps 1–3, every cyclic group of order $n$ (finite or $\infty$) is isomorphic to the same fixed model ($\mathbb{Z}$ or $\mathbb{Z}/n\mathbb{Z}$), so any two cyclic groups of the same order are isomorphic to each other (isomorphism is transitive and symmetric, since composing/inverting bijective homomorphisms gives bijective homomorphisms). Conversely, isomorphic groups have the same cardinality, so groups of different order cannot be isomorphic. This completes the classification. $\blacksquare$

This was proved as Step 2 of the theorem above, via the well-ordering principle and the division algorithm; uniqueness of $n \ge 0$ follows since $n\mathbb Z = m\mathbb Z$ with $n,m \ge 0$ forces $n \mid m$ and $m \mid n$, hence $n = m$. Each $n\mathbb{Z}$ is generated by $n$ by definition, so is cyclic. $\blacksquare$

We use the correspondence with subgroups of $\mathbb Z$ established in the preceding Lemma, transported through the quotient map — a standard and non-circular technique since it only uses facts about $\mathbb{Z}$ already proved.

Setup. Let $\pi: \mathbb{Z} \to \mathbb{Z}/n\mathbb{Z}$ be the canonical surjective homomorphism $\pi(k) = \bar k$, with kernel $n\mathbb{Z}$.

Every subgroup of $G$ is the image of a subgroup of $\mathbb{Z}$ containing $n\mathbb{Z}$. Let $H \leq G$ be any subgroup. Let $\widetilde H = \pi^{-1}(H) = \{k \in \mathbb{Z} : \bar k \in H\}$. This is a subgroup of $\mathbb{Z}$: it contains $0$ (since $\bar 0 = e \in H$), and if $k, l \in \widetilde H$ then $\bar k, \bar l \in H$ so $\overline{k - l} = \bar k - \bar l \in H$ (as $H$ is a subgroup), so $k - l \in \widetilde H$. Also $n\mathbb{Z} \subseteq \widetilde{H}$ since $\pi(n\mathbb Z) = \{\bar 0\} \subseteq H$. By the Lemma, $\widetilde H = m\mathbb{Z}$ for a unique $m \geq 0$; since $n \in n\mathbb Z \subseteq \widetilde H = m\mathbb{Z}$ and $n > 0$, we must have $m > 0$ and $m \mid n$ (because $n \in m\mathbb{Z}$ means $m$ divides $n$). Then

So every subgroup $H$ of $G$ is cyclic, generated by $\bar m$ for some positive divisor $m$ of $n$.

Order of $H = \langle \bar m\rangle$. The order of $\bar m$ in $G$ is the least positive $t$ with $t m \equiv 0 \pmod n$, i.e. the least positive $t$ with $n \mid tm$, i.e. $t = n/\gcd(m,n)$. Since $m \mid n$, $\gcd(m,n) = m$, so the order of $\bar m$, and hence of $H = \langle \bar m \rangle$, is exactly $n/m$. Writing $d = n/m$ (a positive divisor of $n$, since $m \mid n$), we get $|H| = d$ and $H = \langle \overline{n/d}\rangle = H_d$ as defined in the statement.

Existence for every divisor $d \mid n$. Given any positive divisor $d$ of $n$, set $m = n/d$ (also a positive divisor of $n$); then $H_d := \langle \bar m \rangle$ is a subgroup of order $d$ by the computation above. This proves existence.

Uniqueness for each order $d$. Suppose $H, H'$ are both subgroups of $G$ of order $d \mid n$. By the argument above, $H = \langle \overline{n/d}\rangle$ and $H' = \langle \overline{n/d'}\rangle$ where $d, d'$ are both forced (by the order computation) to equal the actual order of the respective subgroup; since both have order $d$, both equal $\langle \overline{n/d} \rangle = H_d$. Hence $H = H'$: there is only one subgroup of each order $d \mid n$.

Bijectivity of $d \mapsto H_d$. We have shown: every subgroup of $G$ equals $H_d$ for a unique divisor $d \mid n$ (its order), and every divisor $d \mid n$ gives rise to exactly one subgroup $H_d$. So $d \mapsto H_d$ is a bijection from positive divisors of $n$ to subgroups of $G$.

Inclusion reflects divisibility. Suppose $d_1 \mid d_2$, both dividing $n$. Write $d_2 = d_1 e$. Then

Since $n/d_1 = e \cdot (n/d_2)$, the generator of $H_{d_1}$ is an integer multiple of the generator of $H_{d_2}$ modulo $n$ — more precisely $\overline{n/d_1} = e\cdot \overline{n/d_2} \in H_{d_2}$ — so $H_{d_1} \subseteq H_{d_2}$ (as $H_{d_2}$ is closed under taking multiples of its generator, being a subgroup generated by it). Conversely if $H_{d_1} \subseteq H_{d_2}$ then since $|H_{d_1}| = d_1$ divides $|H_{d_2}| = d_2$ by Lagrange's Theorem (a subgroup's order divides the group's order), we get $d_1 \mid d_2$. So $H_{d_1} \subseteq H_{d_2} \iff d_1 \mid d_2$, exhibiting the bijection $d \mapsto H_d$ as an order isomorphism between the divisor poset of $n$ and the subgroup poset of $G$ under inclusion. $\blacksquare$

By the subgroup-order computation in the proof of the Divisor Lattice theorem (applied with $m$ replaced by $a$, not assumed to divide $n$; the same computation generalizes): the order of $\bar a$ in $\mathbb{Z}/n\mathbb{Z}$ is $n/\gcd(a,n)$. Indeed, the order is the least positive $t$ with $n \mid ta$; writing $g=\gcd(a,n)$, $a = g a'$, $n = g n'$ with $\gcd(a',n')=1$, the condition $n \mid ta$ becomes $gn' \mid tga'$, i.e. $n' \mid ta'$, and since $\gcd(a',n')=1$ this forces $n' \mid t$; the least such positive $t$ is $t=n'=n/g$. Now $\bar a$ generates $\mathbb{Z}/n\mathbb{Z}$ iff $\langle \bar a\rangle$ has order $n$ (equal to the whole group), i.e. iff $n/\gcd(a,n) = n$, i.e. iff $\gcd(a,n)=1$. The number of generators is therefore the number of $a \in \{0,1,\dots,n-1\}$ (a complete set of representatives) with $\gcd(a,n)=1$, which is exactly the definition of $\varphi(n)$. $\blacksquare$