Prove subgroups of cyclic groups are cyclic without division algorithm, rings, homomorphisms or $\gcd$ of infinite numbers? 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.


*

*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?

*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$$


*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.
 A: 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.
A: 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$.
