# A subgroup of a cyclic group is cyclic - Understanding Proof

I'm having some trouble understanding the proof of the following theorem

A subgroup of a cyclic group is cyclic

I will list each step of the proof in my textbook and indicate the places that I'm confused and hopefully somewhere out there can clear some things up for me.

Proof

Let $$G$$ be a cyclic group generated by "$$a$$" and let $$H$$ be a subgroup of $$G$$. If $$H = {\{e\}}$$, then $$H = \langle e\rangle$$ is cyclic. If $$H \neq \space {\{e\}}$$, then $$a^n \in H$$ for some $$n \in \mathbb{Z}^{+}$$. Let $$m$$ be the smallest integer in $$\mathbb{Z}^{+}$$ such that $$a^m \in H$$.

We claim that $$c = a^m$$ generates $$H$$; that is,

$$H = \langle a^m\rangle = \langle c\rangle.$$

We must show that every $$b \in H$$ is a power of $$c$$. Since $$b \in H$$ and $$H \leq G$$, we have $$b = a^n$$ for some $$n$$. Find $$q$$ and $$r$$ such that

$$n = mq + r \space \space \space \space for \space \space \space 0 \leq r < m,$$

Alright this is the first part in the proof where I start to get confused. Where does the division algorithm come from and why are we using it? The proof continues as follows:

$$a^n = a^{mq + r} = (a^m)^q \cdot a^r,$$

so

$$a^r = (a^m)^{-q} \cdot a^n.$$

Now since $$a^n \in H$$, $$a^m \in H$$, and $$H$$ is a group, both $$(a^m)^{-q}$$ and $$a^n$$ are in $$H$$. Thus

$$(a^m)^{-q} \cdot a^n \in H; \space \space \space \text{that is,} \space \space a^r \in H.$$

This is another point at which I’m a little confused. What exactly about $$a^n$$ and $$a^m$$ being elements of $$H$$ allows us to accept that $$(a^m)^{-q}$$ and $$a^{n}$$ are in $$H$$? The proof continues:

Since $$m$$ was the smallest positive integer such that $$a^m \in H$$ and $$0$$ $$\leq r$$ $$< m$$, we must have $$r = 0$$. Thus $$n = qm$$ and

$$b \space = \space a^n \space = \space (a^m)^q \space = \space c^q,$$

so $$b$$ is a power of $$c.$$

This final step is confusing as well, but I think its just because of the previous parts I was confused about. Any help in understanding this proof would be greatly appreciated

• "Where does the division algorithm come from?" is a very vague question. In this cases, there is a deeper theorem involved, that is hidden because you are talking about groups rather than the (possibly later topic) rings, name that the integers are something called a "principal ideal ring." The division algorithm is deeply entwined with this property. Feb 5, 2013 at 17:19
• What textbook is this? This is a nice proof. Jun 1, 2017 at 3:57
• Could you advise which textbook this was adapted from? Thanks. Sep 11, 2018 at 10:48
• For the questions under the main question regarding where the proof came from, the book where this proof is from is: A First Course in Abstract Algebra by John B.Fraleigh. I know this does not answer the main question, whoever can add comments could move this there. Jan 24, 2020 at 18:59

For the first question, the appearance of the division algorithm is best explained by its usefulness in the rest of the proof. You might think of it because you want $n=qm$, as you need to show that $a^n$ is a power of $a^m$, but the best you can do at that point is say $n=qm+r$ and then attempt to prove $r=0$.

For the second question, as $a^m\in H$, we have $(a^m)^{-1}\in H$, as subgroups are closed under taking inverses, and then $(a^m)^{-q}=((a^m)^{-1})^q\in H$, as subgroups are closed under multiplication.

• .@Matt Can you please explain how r =0 in this proof ....i havenot understood following two lines from proof.....< Since m was the smallest positive integer such that am∈H and 0 ≤r <m, we must have r=0. Thus n=qm > thanks Apr 3, 2015 at 10:37
• You assume $m$ is the smallest positive integer such that $a^m\in H$, but then find that $a^r\in H$, and $r<m$. The only way this is possible is if $r=0$.
– mdp
Apr 3, 2015 at 10:50

First, the use of the division algorithm is for the sake of utility, as it provides a basis for the structure of the proof. Here, we want to relate $n$ with $m$, that is, we want to show that $n$ must be a multiple of $m$, but we start with the fact that what we know of any $n$, then given any positive integer $m$, by the division algorithm, there exist unique integers integers $q$ and $r$, where $0\leq r\lt m$ such that $n = mq + r$.

Essentially that means for any $n$, if we divide by a positive integer $m$, we have a unique integer quotient $q$ and a unique integer remainder $r$ where $0\leq r \lt m$. So to show that $m$ is a multiple of $n$ (no remainder), we want to show that $n = qm + 0$. I.e. we want $n=qm$, in order to show that $a^n$ is a power of $a^m$, but at most we can start with the fact that $n=qm+r$. The objective then is to prove that $r=0$.

For the second question, since $a^m\in H$, it follows $(a^m)^{-1}\in H$, since subgroups are closed under taking inverses. Then, since $a^m, (a^m)^{-1} \in H$, $(a^m)^{-q}=((a^m)^{-1})^q\in H$, since subgroups are closed under multiplication.

Does this clarify matters any?

In the first answer given, at the last part, $$a^r$$ is a member of $$H$$, and $$0\le r. Since $$a^r$$ is a member of $$H$$ and $$a^m$$ is a member of $$H$$ where $$m$$ is the smallest integer s.t. $$a^m$$ belongs to $$H$$.

Thus $$r>m$$. However $$r, by Euclid's division lemma. Hence, due to this contradiction, $$r=0$$, and $$n=qm$$.

a nontrivial cyclic group is a group with a singleton generating set, and vice versa.

let H be a cyclic group, and suppose $K$ is a non-cyclic subgroup.

evidently $K$ is a proper subgroup of H and has no set of generators of cardinality less than 2.

choose a generator $h$ for H.

in examining generating sets for $K$, we may exclude any containing the identity.

and since $K$ is proper no generating set contains $h$

for $K$ choose a generating set $\mathfrak{K}$ which contains an element $h^m$ where $m \gt 1$ is minimal amongst all the powers of $h$ occurring in generating sets for K.

without loss of generality we may assume that for any $p \gt 1$ we have $h^{pm} \notin \mathfrak{K}$

since $|\mathfrak{K}| \ge 2$

$$\exists n \gt m.h^n \in \mathfrak{K}$$ define $a \ge 1$ by $$a = \max\{b|bm \lt n\}$$ it follows that: $$0 \lt n-am \lt m$$ but since $h^{n-am}=h^n (h^m)^{-a} \in K$ it follows that $\mathfrak{K}'=\mathfrak{K} \cup \{h^{n-am}\}$ is a generating set for $K$ contradicting the minimality in our choice of $m$