# Prove that subgroup of cyclic group is generated by the following:

I am having trouble with the last part of this. From LaGrange's theorem, n divides m. I am not sure how to prove the last part though.

Let $G$ be a finite cyclic group of order $m$ generated by $g$. Let $H$ be a subgroup of $G$ of order $n$. Prove that $n|m$ and that $H$ is generated by $g^{m/n}$

Any help is appreciated!

Order the elements of $G$ as follows : $G = \{1,g,g^2,\cdots,g^{m-1}\}$. If $H$ is a subgroup of order $n$, you suspect (this is no proof) that the elements of $H$ will be $\{1,g^{m/n},g^{2m/n},\cdots,g^{(n-1)m/n} \}$. An equivalent statement to this is that $g^{m/n}$ generates $H$. We will prove this.

Label the elements of $G$ as follows : $1 = x_0$, $g = x_1$, $\cdots, g^{m-1} = x_{m-1}$. Let $h \in H$ be the element of $H$ with the smallest positive label (positive meaning $> 0$ here). Now we know that $x_i^k = x_{ki}$ as long as $ki < m$. Let $i_0$ be the label of $h$ and assume $x_j \in H$. By the Euclidean algorithm, we can write $j = i_0 \alpha + \beta$ with $0 \le \beta < i_0$. If $\beta \neq 0$, we have $$x_{\beta} = x_j x_{i_0}^{-\alpha} \in H,$$ contradicting the fact that $h = x_{i_0}$ has the smallest positive label. Therefore $\beta = 0$ and $x_j = x_{i_0}^{\alpha}$. Therefore $H$ is generated by $x_{i_0} = g^{i_0}$, hence $H$ is cyclic. Since the subgroup generated by $g^{i_0}$ has order $n$, we must have $i_0 = m/n$.

(P.S. : You don't need the labelling process, but I just thought it would make it easier to distinguish the exponents put on $g$ from the elements themselves.)

Hope that helps,

• Thank you so much, just a question, when you first saw the claim, is it something that is intuitively true to you? When I look at it, I am not sure why it should hold true, what is your intuition behind the proof? THanks Oct 22, 2015 at 4:13
• @LostStudent : It is not hard to show that any finite cyclic group $G$ is isomorphic to $\mathbb Z / n \mathbb Z$ where $n = |G|$. My intuition therefore comes from this example since addition is easier to understand. Oct 23, 2015 at 2:03

First, if $H=\{1\}$, then $H$ is generated by $g^{m/1}=1$. Otherwise, let $S=\{k\in[1,m-1]\mid g^k\in H\}$. Then, $S$ is a nonempty subset of $\mathbb{Z}$ which is bounded below. By the well-ordering principle, $S$ has a least element $d$.

We claim that $H=\langle g^d\rangle$. Indeed, if $g^k\in H$ for $k>0$, then using the division algorithm, $k=qd+r$ with $0\leq r<d$. If $r\neq 0$, then $g^r=(g^d)^{-q}g^k\in H$. Hence, $r\in S$, contradicting the minimality of $d$. Therefore $r=0$ and $H=\langle g^d\rangle$ as required.

Now, as $|H|=|g^d|=n$, we have $dn=m$, and $d=m/n$.

You can also look at the epimorphism $\pi:\Bbb{Z}\to\Bbb{Z}/m\Bbb{Z}$, we have for any subgroup $K$ of $\Bbb{Z}/m\Bbb{Z} : K=\pi(\pi^{-1}(K))$ so that $K$ is the image of an infinite cyclic group because $\pi^{-1}(K)$ is a subgroup of $\Bbb{Z}$, so it's as the form $n\Bbb{Z}$ for a unique integer $n$. Hence, $K$ is a finite cyclic group generated by $\pi(n)$.

Now, as $K$ is a subgroup of $\Bbb{Z}/m\Bbb{Z}, \pi(0)=\overline{0}$ is in $K$, therefore, we have $$\pi^{-1}(0)\subset \pi^{-1}(K),$$

this means that $n|m>$

What is the order of $K$? $o(K)=o(\overline{n})$, but the order of $\overline{n}$ is the smallest integer $d>0$ such that $d\overline{n}=o(0)$, as $d\overline{n}=\pi(dn)$, necessarily $d=m/n.$

• The proof that all subgroups of $\mathbb Z$ are cyclic ultimately relies on the Euclidean algorithm. This proof usually needs to be done in a first course in group theory, so in some sense your proof might be considered a bit too "advanced". Oct 20, 2015 at 21:34
• I second @PatrickDaSilva here. The whole point of a question like this is that it can be tackled with a minimal amount of tools. Moreover, the argument becomes somewhat circular at the end. Why is it ok to just look at Z/mZ? Why is $\pi^{-1}(K) a subgroup? Most importantly, why is K cyclically generated? Oct 20, 2015 at 23:39 • @DavidHill can be but not must be right ? I pretty sure if he knows Lagrange's theorem then he also has in mind why$\pi^{-1}(K)$is q subgroup and why$\pi(x^k)=\pi(x)^k\$.. Oct 21, 2015 at 6:57
• @PatrickDaSilva I am a student on first course in group theory, and I think if the OP knows Lagrange's thereom then my proof it's not so advanced, but yes the usual proof use the Euclidean algorithm :). Oct 21, 2015 at 7:00
• @user281591 : By advanced I only meant that it was assuming something that should normally be proved at this stage, not that the proof was too hard for the OP Oct 21, 2015 at 7:02