# Role of Well-Ordering Principle in proving every subgroup of $\mathbb{Z}$ is of the form $n\mathbb{Z}$

Problem: Let $n = 0, 1, 2, \dots$ and $n\mathbb{Z} = \left\{nk : k \in \mathbb{Z}\right\}$. Show that these subgroups are the only subgroups of $\mathbb{Z}$.

I understood most of the proof, but I do not see why the Well-Ordering Principle comes in so soon in the argument. I mean, I know it is necessary to argue for the case of $m$, but my professor said that the minimal is needed to argue for the multiples of $n$ is in $n\mathbb{Z}$. Can anyone help me to understand the role of the Well-Ordering principle?

Here is the proof:

We want to show that all subgroups of $\mathbb{Z}$ are of the form $n\mathbb{Z}$ with $n \in \mathbb{N} \cup \left\{0\right\}$. Suppose $H \subseteq \mathbb{Z}$ is a subgroup. If $H = \left\{0\right\}$, then $H = 0\mathbb{Z}$. Suppose $H\neq\left\{0\right\}$. By the Well-Ordering principle, there exists a nonzero element $n \in H$ such that $|n|$ is minimal. Since $H$ is a subgroup of $\mathbb{Z}$, then the inverse of $n$ is also in $H$, i.e., $−n \in H.$ Since $n$ and $−n$ are in $H$, we can assume without loss of generality that $n$ is positive. Since $H$ is a subgroup, all multiples of $n$ must be in $H$. This means that $n\mathbb{Z} \subseteq H$. Now suppose that there is an element $m \in H$ such that $m \not\in n\mathbb{Z}$. By the division algorithm, there exist unique integers $q$ and $r$ such that:

$$m = qn + r,$$

where $0 < r < n$. Since $m \not\in n\mathbb{Z}$, $r \neq 0$. Since $m \in H$ and $qn \in H$, then $−qn \in H,$ so $m − qn \in H.$ Therefore $r \in H.$ But $0 < r < n$ which contradicts the minimality of $n$. This means no such element $m$ exists. That proves that $H = n\mathbb{Z}$.

If $H \neq {0}$, then there exists some non-zero integer $m$ in $H$. Since $H$ is a subgroup, $-m$ is also in $H$, and all multiples of $m$ and $-m$ are in $H$. In other words, $|m|\mathbb{Z} \subseteq H$.
This is the best we can do without invoking the Well-Ordering Principle. We have still not managed to get an equality, that is, we haven’t found a positive integer $n$ such that $n\mathbb{Z} = H$.
The idea behind using the Well-Ordering Principle here is the following. Let’s take a subgroup of $\mathbb{Z}$ of the form $k\mathbb{Z}$ for some positive integer $k$. Then, $k$ is also the smallest positive integer in the subgroup $k\mathbb{Z}$. So, if we search for the smallest positive integer $n$ in $H$, then we guess (correctly) that we might be able to show $H = n\mathbb{Z}$ for this $n$. This is done using the division algorithm as you have shown in the proof.
• Oh, it made sense now. My professor using an example that if we start with $2Z \subset H,$ then we will end up with $4Z \subset H$, thus we need minimal value of $n$. However, that did not make sense for me at all. Jan 26 '18 at 5:11