## 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 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*}