2
$\begingroup$

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.

$\endgroup$

4 Answers 4

3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.