Why does the Principle of Well-Ordering imply a remainder of $0$ for the division algorithm?

Question

I'm currently reading a text (Thomas W. Judson, Abstract Algebra - Theory and Applications) where the author proofs the theorem that every subgroup of a cyclic group is cyclic. The proof goes as follows:

The main tools used in this proof are the division algorithm and the Principle of Well-Ordering. Let $G$ be a cyclic group generated by a and suppose that $H$ is a subgroup of $G$. If $H = {e}$, then trivially $H$ is cyclic. Suppose that $H$ contains some other element $g$ distinct from the identity. Then $g$ can be written as an for some integer $n$. We can assume that $n > 0$.

Let $m$ be the smallest natural number such that $a^m \in H$. Such an $m$ exists by the Principle of Well-Ordering. We claim that $h = a^m$ is a generator for $H$. We must show that every $h' \in H$ can be written as a power of $h$.

Since $h' \in H$ and $H$ is a subgroup of $G$, $h' = a^k$ for some positive integer $k$. Using the division algorithm, we can find numbers $q$ and $r$ such that $k = mq + r$ where $0 \leq r < m$; hence, $$a^k = a^{mq+r}= (a^m)^qa^r = h^qa^r$$ So $a^r = a^kh^{-􀀀q}$. Since $a^k$ and $h􀀀^q$ are in $H$, $a^r$ must also be in $H$. However, $m$ was the smallest positive number such that $a^m$ was in $H$; consequently, $\mathbf{r = 0}$ and so $k = mq$. Therefore, $$h' = a^k = a^{mq} = h^q$$ and $H$ is generated by $h$.

I am trying to understand why one should set $r$ to $0$ if $m$ was the least element.

Since $m$ is a natural number, would setting $r$ to $0$ contradict $m$ being the least natural number, since $0 < m$? Or is the purpose of setting $r$ to $0$ to assign a non-natural value to $r$ for some reason?

Answer 1

The conclusion is that $a^r \in H$, where $0 \le r < m$, and $m$ is the smallest positive integer (note: positive integer, not just non-negative integer) such that $a^m \in H$. If $r \neq 0$, then $r$ is positive, and therefore $r$ is a smaller positive number than $m$ such that $a^r \in H$. This is a contradiction, so $r = 0$.

The only place a well-ordering is used is establishing the existence of $m$. This is just due to the well-ordering of the natural numbers; the set of positive numbers $k$ such that $a^k \in H$ forms a non-empty subset of the natural numbers, hence it has a minimal element.

I'm not really that keen on saying "by the Principle of Well-Ordering" because, to me, that refers to the theorem, equivalent to the axiom of choice, which states that every set has a (possibly bizarre, unconstructable) well-ordering. But, I think it's clear what the author is referring to.