$\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&}$

## Section4.2Subgroups of a Cyclic Group

We can ask some interesting questions about cyclic subgroups of a group and subgroups of a cyclic group. If $G$ is a group, which subgroups of $G$ are cyclic? If $G$ is a cyclic group, what type of subgroups does $G$ possess?

The main tools used in this proof are the division algorithm and the Principle of Well-Ordering. Let $G$ be a cyclic group generated by $a$ and suppose that $H$ is a subgroup of $G\text{.}$ If $H = \{ e \}\text{,}$ then trivially $H$ is cyclic. Suppose that $H$ contains some other element $g$ distinct from the identity. Then $g$ can be written as $a^n$ for some integer $n\text{.}$ Since $H$ is a subgroup, $g^{-1} = a^{n}$ must also be in $H\text{.}$ Since either $n$ or $-n$ is postive, we can assume that $H$ contains positve powers of $a$ and $n \gt 0\text{.}$ Let $m$ be the smallest natural number such that $a^m \in H\text{.}$ Such an $m$ exists by the Principle of Well-Ordering.

We claim that $h = a^m$ is a generator for $H\text{.}$ We must show that every $h' \in H$ can be written as a power of $h\text{.}$ Since $h' \in H$ and $H$ is a subgroup of $G\text{,}$ $h' = a^k$ for some integer $k\text{.}$ Using the division algorithm, we can find numbers $q$ and $r$ such that $k = mq +r$ where $0 \leq r \lt m\text{;}$ hence,

\begin{equation*} a^k = a^{mq +r} = (a^m)^q a^r = h^q a^r. \end{equation*}

So $a^r = a^k h^{-q}\text{.}$ Since $a^k$ and $h^{-q}$ are in $H\text{,}$ $a^r$ must also be in $H\text{.}$ However, $m$ was the smallest positive number such that $a^m$ was in $H\text{;}$ consequently, $r=0$ and so $k=mq\text{.}$ Therefore,

\begin{equation*} h' = a^k = a^{mq} = h^q \end{equation*}

and $H$ is generated by $h\text{.}$

First suppose that $a^k=e\text{.}$ By the division algorithm, $k = nq + r$ where $0 \leq r \lt n\text{;}$ hence,

\begin{equation*} e = a^k = a^{nq + r} = a^{nq} a^r = e a^r = a^r. \end{equation*}

Since the smallest positive integer $m$ such that $a^m = e$ is $n\text{,}$ $r= 0\text{.}$

Conversely, if $n$ divides $k\text{,}$ then $k=ns$ for some integer $s\text{.}$ Consequently,

\begin{equation*} a^k = a^{ns} = (a^n)^s = e^s = e. \end{equation*}

We wish to find the smallest integer $m$ such that $e = b^m = a^{km}\text{.}$ By Proposition Proposition 4.2.3, this is the smallest integer $m$ such that $n$ divides $km$ or, equivalently, $n/d$ divides $m(k/d)\text{.}$ Since $d$ is the greatest common divisor of $n$ and $k\text{,}$ $n/d$ and $k/d$ are relatively prime. Hence, for $n/d$ to divide $m(k/d)$ it must divide $m\text{.}$ The smallest such $m$ is $n/d\text{.}$

Let us examine the group ${\mathbb Z}_{16}\text{.}$ The numbers 1, 3, 5, 7, 9, 11, 13, and 15 are the elements of ${\mathbb Z}_{16}$ that are relatively prime to 16. Each of these elements generates ${\mathbb Z}_{16}\text{.}$ For example,

\begin{align*} 1 \cdot 9 & = 9 & 2 \cdot 9 & = 2 & 3 \cdot 9 & = 11\\ 4 \cdot 9 & = 4 & 5 \cdot 9 & = 13 & 6 \cdot 9 & = 6 \\ 7 \cdot 9 & = 15 & 8 \cdot 9 & = 8 & 9 \cdot 9 & = 1 \\ 10 \cdot 9 & = 10 & 11 \cdot 9 & = 3 & 12 \cdot 9 & = 12\\ 13 \cdot 9 & = 5 & 14 \cdot 9 & = 14 & 15 \cdot 9 & = 7. \end{align*}