# How to show every subgroup of a cyclic group is cyclic?

I'm teaching a group theory course now, and I wanted to give my students a proof that every subgroup of a cyclic group is cyclic. The easiest way I could think to do this is to say that any cyclic group corresponds to a $\mathbb{Z}/n\mathbb{Z}$ and then (implicitly) use the first isomorphism theorem (which they haven't learned yet) to "reduce" it to the theorem that every subgroup of $\mathbb{Z}$ is of the form $m\mathbb{Z}$. The problem is that this latest statement is not simple at all (every subgroup is an ideal, and $\mathbb{Z}$ is a PID because $\mathbb{Z}$ is Euclidean).

This all seems way too convoluted for such an easy statement. What's the simplest most elementary proof that I can give?

-
"The problem is that this latest statement is not simple at all" What the ...? You can just repeat the arguments without these ring-theoretic notions (see the given answers below) –  Martin Brandenburg Oct 17 '10 at 15:32

If you accept Lagrange's theorem and the existence of quotient groups, there's another argument in the finite case. Let $G=\langle a\rangle$ be a cyclic group of order $n$. By Lagrange's theorem if $H$ is a subgroup of $G$ then $m=|H|$ is a factor of $n$, and is $m\mid n$ then $H_m=\langle a^{n/m}\rangle$ is a subgroup of order $m$. I claim $G$ has no other order $m$ subgroup. The group $G/H$ has order $n/m$ so $x^{n/m}=e$ for all $x\in G/H$. This translates to $x^{n/m}\in H$ for all $x\in G$ which means $H_m\le H$. These have the same order so $H=H_m$.

-
I think this is a nice answer, and I upvoted it. But from a pedagogical perspective: I do not advise that anyone give this proof in a first course on group theory! The idea of quotient group alone is complicated enough so that many students will find this proof confusing. –  Pete L. Clark Oct 17 '10 at 18:10
As a beginning algebra student, quotient groups were by far the most difficult concept for me to grasp, much more difficult than the ideas used in the original proof provided above. But yes, nice proof. +1 –  BBischof Oct 17 '10 at 18:33
+1: this was the proof my professor gave us in our group theory course the first year! :D –  Andy Oct 18 '10 at 3:34

If the original group is generated by $a$, and $d$ is the least positive integer such that $a^d$ is in the subgroup, then show using the division algorithm that $a^d$ generates the subgroup.

To elaborate, the division algorithm says:

If $m$ and $n$ are integers and $n$ is positive, then there are unique integers $q$ and $r$ such that $m=nq+r$ and $0\leq r\lt n$.

You could prove this by taking $r$ to be the least nonnegative integer expressible in the form $m-np$ as $p$ ranges over the integers, which then determines $q$. (There are details here which I am omitting.)

Suppose $G$ is a cyclic group (finite or infinite) with generator $a$, i.e., $G=\langle a\rangle$. Let $H$ be a subgroup of $G$. Let $d$ be the smallest element of the set of positive integers $n$ such that $a^n$ is in $H$. (Unless $G$ is infinite and $H$ is trivial, this exists.) If $b$ is an arbitrary element of $H$, then because $b$ is in $G$, $b=a^m$ for some integer $m$. Apply the division algorithm to write $m=dq+r$ for integers $q$ and $r$ with $0\leq r\lt d$. Then $b=a^m=(a^d)^q\cdot a^r$. Since $b$ is in $H$ and $a^d$ is in $H$, it follows that $a^r=a^m\cdot(a^d)^{-q}$ is in $H$. If $r$ were positive, this would contradict the choice of $d$, so $r=0$, and $b=a^m=(a^d)^q$. Since $b$ was arbitrary, this shows that $H\subseteq \langle a^d\rangle$.

-
It seems that proving that is equivalent to my proof. No? –  Shelly Oct 17 '10 at 3:54
This proof works for the infinite case as well, whereas you seem to want to use that case in your proof. I'm not really sure what your proof is, but my answer gives the proof as I learned it in my first abstract algebra class, and which is the most elementary I can think of. Obviously I have left out the details, but I could include them if it would be more helpful. –  Jonas Meyer Oct 17 '10 at 3:59
No, it's fine. I'm looking to avoid the division (euclidean) algorithm... –  Shelly Oct 17 '10 at 4:03
@Shelly: I don't think you will be able to avoid the division algorithm, even if you try it "your way": to prove that every subgroup of $\mathbb{Z}$ is of the form $m\mathbb{Z}$ is essentially to use the division algorithm: you prove it by letting $m$ be the least positive integer that lies in the subgroup, and then showing (by considering division with remainder) that every element in the subgroup is a multiple of $m$. So it's really just a question of whether you want to do it "in the exponents", or you want to take discrete logs and do it in the integers. It's the exact same argument. –  Arturo Magidin Oct 17 '10 at 4:11
@Shelly: but how do you prove that the subgroup of $\mathbb{Z}$ generated by $a$ and $b$ is generated by $\gcd(a,b)$? At the very least, you need to show that the gcd is a linear combination of $a$ and $b$. How do you do that without division-with-remainder? It seems to me that by trying to avoid a pretty simple fact that students are very familiar with (division with remainder of positive integers), you are only hiding it inside much more difficult and less elementary proofs. –  Arturo Magidin Oct 17 '10 at 4:23

It is enough to show that every maximal proper subgroup $H$ of $G$ is cyclic, by induction; to start the induction, notice that if $G$ is simple, then there is nothing to prove.

So let $H\subset G$ be a maximal proper subgroup, so that $G/H$ is simple. There exists then a prime $p$ such that $G/H$ is isomorphic to $\mathbb Z/p\mathbb Z$ and then $pG\subset H$. From the exact sequence of abelian groups $$0\to H\to G\to G/H\to 0$$ we get the exact sequence $$0\to H/pG\to G/pG\to G/H\to 0.$$ Now this is an exact sequence of $\mathbb F_p$-vector spaces in an obvious way, and $G/H$ and $G/pG$ are vector spaces of dimension $1$ (for the first, this is obvious; for the second, it is enough to notice that $G/pG$ is cyclic as an abelian group and non-zero because it surjects onto $G/H$) It follows that $H/pG=0$, i.e., that $H=pG$. Since $G$ is cyclic, then $H$ is cyclic too.

-
This seems like an awfully sophisticated proof for this simple fact! –  Pete L. Clark Oct 17 '10 at 10:10
Upon further reflection, this answer seems to be a reasonable rebuttal to the first sentence (even in its modified, weakened form) of the following answer Greg Kuperberg gave on MO recently: mathoverflow.net/questions/41958/no-simple-groups-of-order-720/…. So...+1. –  Pete L. Clark Oct 17 '10 at 12:28
@Pete: this is really just the result of playfully looking for a proof not based on Euclidean division, and should be taken not too seriously! –  Mariano Suárez-Alvarez Oct 17 '10 at 14:53
don't worry, I'm not taking it too seriously. –  Pete L. Clark Oct 17 '10 at 17:40

See Proposition 5 in

http://www.math.uga.edu/~pete/4400algebra2point5.pdf

Note that part of this argument is left as an exercise for the reader. It is an incarnation of the same argument that shows that a Euclidean domain is a PID, but one certainly doesn't need this terminology or any prior results. Namely, one is supposed to show that -- upon identifying the elements of a cyclic group $Z_n$ with the integers $0,1,\ldots,n-1$ as usual -- if $H$ is a nontrivial subgroup of $Z_n$, then it is generated by its smallest nonzero element, say $k$. Why? Well, if not, there would exist an element $\ell$ of the subgroup which is not a multiple of $k$, and then by subtracting off a suitable multiple of $k$ -- to be completely explicit, let $a$ be the largest non-negative integer $a$ such that $\ell - ak$ is positive, and subtract $ak$ -- we get an element of the subgroup which is positive but smaller than $k$, contradiction.

Note that the more explicitly ring-theoretic proof you have in mind is the one alluded to in the Remark at the bottom of page 2.

-

A simple way to present this and related results is to employ concrete fractional models of cyclic groups, i.e. $\rm\ C_n\: =\: \frac{1}n\mathbb Z\ \:(mod\ \mathbb Z)\ =\ \{ 0,\: 1/n,\: 2/n,\: \ldots,\: (n-1)/n\}\:.\$ Suppose $\rm G$ is a nontrivial subgroup. Since $\rm G\:$ is closed under subtraction, every element of $\rm G\:$ must be an integer multiple of its least element $\rm\:g\:$ (else if $\rm\: h\:$ were the least nonmultiple, then $\rm\: h - g\:$ would be a smaller one). Thus $\rm\:G = \langle g \rangle\:$ is cyclic. $\$ QED

-

Let's take $H$ a subgroup of $(Z/nZ,+)$. You can write $H=\{0, i_1,i_2, ..., i_r\}$ such that $0<i_1<i_2<i_3<...<i_r<n$.

Now I claim that $i_2 = 2 i_1$. Since $H$ is a group, $i_2-i_1 \in H$, and $i_2 > i_2-i_1 > 0$. Obviously, $i_2 - i_1 = i_1$.

Now we prove that $i_3=3i_1$ : $i_3-i_1 \in H$ and $i_3 > i_3 - i_1 > 0$. So $i_3-i_1 = i_2$ or $i_3-i_1 = i_1$. In the second case, $i_3 = i_2$ which is false. So $i_3=i_2+i_1 =3i_1$.

I think now it's easy to prove by induction that $i_k = ki_1$ for all $1\leq k \leq r$.

-
Let G be a group. By definition, any quotient group H of G is realized by a surjective homomorphism $\phi: G \twoheadrightarrow H$.
Now suppose $G = \langle x \rangle$. Then, since $\phi$ is surjective, $H = \langle \phi (x) \rangle$.