Prove subgroups of cyclic groups are cyclic without division algorithm, rings, homomorphisms or $\gcd$ of infinite numbers?

Question

I have found a lot of proofs on this site, on proofwiki and elsewhere. I thought of my own which was unlike all I found except for 1 proof (I have linked it below.) and was wondering if I could get anywhere with it.

Let $G$ be a cyclic group generated by $x$. Let $G=\langle x \rangle$. Let $H$ be a subgroup of $G$. If $H$ is trivial, we're done. Otherwise, $\exists n \in \mathbb Z$ s.t. $x^n \in H, n \ne 0$. By definition of a subgroup, $\langle x^n \rangle$ is a subgroup of $H$. If $\langle x^n \rangle \ne H$, then consider $x^{n_1} \in H \setminus \langle x^n \rangle$ to get $\langle x^{n_1} \rangle$ is a subgroup of $H$. If $\gcd({n_1},n)=1$, then $H=G$. Otherwise, $\langle x^{\gcd({n_1},n)} \rangle$ is a subgroup of $H$. If this isn't the whole of $H$, then consider $x^{n_2} \in H \setminus \langle x^{\gcd({n_1},n)} \rangle$ and so on.

I think this process is finite for some reason like we need only consider positive integers less than some positive integer. All we need is 2 relatively prime exponents to get all of $G$, so it seems unlikely that the process is infinite.

1. A thought just came to mind that if it's finite, then it's probably due to the division algorithm? Does anyone know a way to prove finiteness without the division algorithm?

2. If this process is potentially infinite, then why?

The most similar proof I found online was in http://brianbi.ca/artin/2.4 where he lets $H=\{x^i | i \in S\}$ and then considers $d=\gcd_{i \in S}(i)$.

I really feel I'm missing something simple to say somehow

$$\langle x^n \rangle \subseteq H \subseteq \langle x \rangle$$

implies, if $H$ is a subgroup of $\langle x \rangle$, that $H = \langle x^n \rangle$ else some $H = \langle x^m \rangle$ where

$$\langle x^n \rangle \subseteq \langle x^m \rangle \subseteq H \subseteq \langle x \rangle$$

3. Another idea I had was to create a bijection between $\mathbb Z$ and $\langle x \rangle$, but does anyone know a way to go about this without homomorphisms?

Note: The division algorithm is used as part of some proof of some fact used above, so there's no avoiding division algorithm. My intention is to avoid using division algorithm again.

Answer 1

One can actually completely avoid invoking the division algorithm by referring to the well-ordering of natural numbers:

• Let $H$ be a subgroup of $G=\langle x\rangle$. If $H$ contains only the neutral element, we are done.
• Otherwise, let $n$ denote the smallest positive integer for which $x^n\in H$. This is well-defined since $H$ contains at least one non-neutral element and positive integers are well-ordered.
• Let $H'=\langle x^n\rangle$ be the cyclic subgroup generated by $x^n$. If $H=H'$, we are done.
• Otherwise, let $m$ denote the smallest positive integer for which $x^m\in H\ \backslash\ H'$. Again, $m$ is well-defined because the set is non-empty and positive integers are well-ordered.

We are almost done now:

• $1\leq n<m$, since $n$ was the lowest non-trivial exponent in the whole $H$, while $m$ was the lowest in a subset of it and was explicitly prevented from being equal to $n$.
• We have $x^m\in H$ and $x^n\in H$, which implies $x^m\left(x^{-1}\right)^n=x^{m-n}\in H$.
• $x^{m-n}$ must belong to $H'$, for otherwise it would contradict the choice of $m$ choice of $m$ as the minimal exponent within $H\ \backslash\ H'$ (since $(m-n)<m$).
• But since $x^{m-n}\in H'$ and $x^n\in H'$, we must also have $x^{(m-n)+n}=x^m\in H'$; a contradiction with our choice of $m$ as exponent of a $H\ \backslash\ H'$ element.

Of course, the well-ordering principle can also be used to prove that the division algorithm works for non-negative integers first and arrive at the same conclusion by applying it to compute $\gcd$s.

Answer 2

It is important to mention that the fact that every subgroup of $\mathbb{Z}$ is cyclic implies the existence of GCDs, so in some way, asking for proof of "Every subgroup of a cyclic group is cyclic" and the existence of GCDs, from elementary principles, are equivalenc problems:

Let $m,n\in\mathbb{Z}_{>0}$. Consider the subgroup $H=m\mathbb{Z}+n\mathbb{Z}$ of $\mathbb{Z}$. Since it is cyclic, it is of the form $H=d\mathbb{Z}$ for some $d\in\mathbb{Z}$. Since $H\neq 0$ then $d\neq 0$. Changing $d$ by $-d$ if necessary we can assume $d>0$.

Since $m\mathbb{Z}\subseteq d\mathbb{Z}$, then $d|m$, and similarly $d|n$. if $p$ is another divisor of both $m$ and $n$, then $m\mathbb{Z}\subseteq p\mathbb{Z}$, and $n\mathbb{Z}\subseteq p\mathbb{Z}$, so $d\mathbb{Z}=m\mathbb{Z}+n\mathbb{Z}\subseteq p\mathbb{Z}$, which means that $p$ divides $d$. This proves that $d$ is the GCD of $m$ and $n$.