# Subgroup of $\mathbb{Z}$ generated by two positive integers

An exercise from Aluffi's Algebra book.

Let $m,n$ be positive integers and consider the subgroup $\langle m,n\rangle$ of $\mathbb{Z}$ they generate. As a subgroup of $\mathbb{Z}$ it will be equal to $d\mathbb{Z}$ for some positive integer $d$. What is $d$, in relation to $m,n$.

As far as I understand, $\langle m,n\rangle$ will consist of all integers $k_{1}m + k_{2}n$ for $k_{i} \in \mathbb{Z}$. However, it is not clear to me how can all such integers be generated by addition of some $d$ to itself.

Every subgroup of $\mathbb{Z}$ is of the form $a\mathbb{Z}$ for a (unique) $a\ge0$.

The fact can be readily established using the division with remainder. If $H$ is a subgroup and $H\ne\{0\}$ (otherwise $H=0\mathbb{Z}$ is of the required form), let $a$ be the least positive element in $H$. Then $a\mathbb{Z}\subseteq H$ and, if $h\in H$, we have $$h=aq+r$$ for some $q,r\in\mathbb{Z}$ and $0\le r<a$. Since $r=h-aq\in H$, the minimality of $a$ forces $r=0$. So $h=aq\in a\mathbb{Z}$.

Now, in your case, you certainly have $\langle m,n\rangle=d\mathbb{Z}$, for some $d\ge0$. In particular $d=mx+ny$ for some integers $x$ and $y$.

Moreover, $m=m\cdot1+n\cdot0\in d\mathbb{Z}$, so $d$ divides $m$ and, similarly, $d$ divides $n$. Suppose $c$ is a common divisor of $m$ and $n$. Then $m=ch$ and $n=ck$, so $$d=mx+ny=hxc+kyc=(hx+ky)c$$ and so $c$ divides $d$. Thus $d$ is the greatest common divisor of $m$ and $n$.

Hint

Bezout's identity says that there exist some $x,y$ such that $mx+ny=\gcd(m,n)$. Moreover, if some d divides $m$ and $n$, then also divides $mx+ny$.

Claim $1$: $\langle m, n\rangle = \{am + bn: a,b \in \Bbb Z\}$

Certainly this set contains $\{m,n\}$. Suppose $H$ is a subgroup of $\Bbb Z$ containing $\{m,n\}$. By closure, we must have $am = m + m +\cdots + m$ ($a$ times) in $H$ for every $a > 0$ in $\Bbb Z$, and if $a < 0$, we have $am = -(-am)$, where $-am$ is in $H$ by closure, and $-(-am)$ is in $H$ because of existence of inverses. Finally, $0m = 0 \in H$, since any subgroup contains the identity.

So $am \in H$ for all $a \in \Bbb Z$, and similarly with $bn$. By closure (again), every sum $am + bn$ is likewise in $H$. Now we will see that $\{am + bn: a,b \in \Bbb Z\}$ is actually a subgroup of $\Bbb Z$:

Taking $a = b = 0$, we see that $0$ is in this set, and:

$(am + bn) + (a'm + b'n) = (am + a'm) + (bn + b'n) = (a + a')m + (b+b')n$

so we have closure. Finally, if $a,b \in \Bbb Z$, so are $-a,-b$ and thus:

$-(am + bn) = (-a)m + (-b)n$ is in our set, so it possesses all (additive) inverses. Thus $\{am + bn: a,b \in \Bbb Z\}$ is indeed the subgroup generated by the set $\{m,n\}$.

Now since $m > 0$, it is clear that $\langle m,n\rangle$ contains some positive integers. Therefore, it contains a least positive integer, since the natural numbers are well-ordered. Call this least positive element of $\langle m,n\rangle$, $d$.

Claim $2$: $\langle m,n\rangle = d\Bbb Z = \langle d\rangle$.

Since $d \in \langle m,n\rangle$, it is clear that $d\Bbb Z \subseteq \langle m,n\rangle$. What is not so clear is the reverse inclusion, that $d$ divides every element of $\langle m,n\rangle$. We show this by showing $d|m$ and $d|n$.

For suppose $d$ did not divide $m$. Then $m = qd + r$, for some integer $q$ and some integer $0 < r < d$. Now $d = a_0m + b_0n$ for some integers $a_0,b_0$, so:

$r = m - qd = m - q(a_0m - b_0n) = (1 - qa_0)m + (-b_0)n \in \langle m,n\rangle$.

But this contradicts that $d$ is the least positive element of $\langle m,n\rangle$, so $d$ must divide $m$. The proof that $d|n$ is similar, and left to you, dear reader.

Claim $3$: $d = \gcd(m,n)$. By this we mean that if $c > 0$ and $c|m$ and $c|n$, then $c|d$.

Now $d = a_0m + b_0n$. Since $c|m$ and $c|n$, we have $m = cs$, and $n = ct$, for some (positive) integers $s,t$, and:

$d = a_0(cs) + b_0(ct) = c(a_0s + b_0t)$, that is: $c|d$.

A brief comment: the division algorithm, the fact that given two positive integers $a,b$, that there is a unique pair of integers $q,r$ such that $a = qb + r$ with $0 \leq r < b$ is key to all of this. While this may be "intuitively obvious", it's worth looking at, at least once.

If $a < b$, we may take $q = 0$, and $r = a$. If $a = b$, we may take $q = 1$ and $r = 0$. So suppose $a > b$. Now $a = b + (a-b)$. If $0 < a-b < b$, we are done, we can take $q = 1$, and $r = a-b$.

Otherwise, we have two positive numbers $a' = a-b$ and $b$, and we repeat the process. Note that $a' < a$. We have the same cases as before, but it is worthwhile to see what this means "all in all". It might be that $a' = a - b = b$. In this case, $a = 2b$, and we can take $q = 2$ and $r = 0$. That leaves the case $a' > b$. In this case, our repetition of what we did before gives us:

$a' = b + (a' - b)$, and if $a' - b < b$, we can stop here:

$a = b + (a - b) = b + a' = b + b + (a' - b) = 2b + (a' - b)$

$= 2b + ((a - b) - b) = 2b + (a - 2b)$,so we have $q = 2$ and $r = a - 2b$.

If $a - 2b = b$, we can take $q = 3$, and $r = 0$. Otherwise....we continue with $a'' = a - 2b$. We can only do this a finite number of times (since $a$ is finite): we see $a'' < a' < a$ (we keep getting smaller, and we can only go down to $0$), so there is some $n$ with $nb > a$ and $(n-1)b \leq a$, and we can take $q = n-1$, and $r = a - (n-1)b$. This establishes the existence of $q$ and $r$, but not their uniqueness. I urge you to ponder this.

Uniqueness is not hard to show: If $a = qb + r = q'b + r'$, show we must have $r = r'$ (what happens if $r > r'$? Then $r - r' = (q' - q)b$, but $0 < r - r' < r < b$). If $qb = q'b$, then $b(q - q') = 0$, and...?

An even briefer comment on the comment: it may seem like over-kill to go into this much detail, this is actually fairly elementary stuff. However, the techniques used here are just the same for a more general class of structures known as Euclidean domains, which you shall no doubt encounter at some point. In particular, polynomials over a field form such a structure, and you should not be daunted by them-they're very much like our old friend, the integers.

Let $d=\gcd(m,n)$, then $<m,n>=<d>$.