Show that $n\mathbb{Z} + m\mathbb{Z} = h \mathbb{Z}$, where $h = hcf(m,n)$

Question

As the question says. I'm having trouble putting all the pieces together. I've shown that $m$ divides $n$ if and only if $n \Bbb Z$ is a subring of $m \Bbb Z$ and vice versa. does this suffice to show that $n \Bbb Z + m \Bbb Z = d \Bbb Z$ where d is some divisor of $m$ and $n$, and then show that $d$ must be the greatest common divisor? I'm struggling to see what exactly I need to prove/how to put them together.

Answer 1

First of all, every ideal of $\mathbb{Z}$ is of the form $a\mathbb{Z}$, for a unique integer $a\ge0$, so $n\mathbb{Z}+m\mathbb{Z}=h\mathbb{Z}$, for a unique $h\ge0$. However, we can dismiss the case $h=0$ as very easy: if $h=0$, then also $n=m=0$.

You want to show that $h$ is the greatest common divisor (highest common factor) of $n$ and $m$.

Let's prove that $h$ divides both $n$ and $m$. Indeed, $n=n1+m0\in n\mathbb{Z}+m\mathbb{Z}=h\mathbb{Z}$, so $n=hr$, for some integer $r$. Similarly, $h$ divides $m$.

Note also that $h=na+mb$, for some integers $a$ and $b$, by definition of $n\mathbb{Z}+m\mathbb{Z}$. Suppose $k$ is a (positive) common divisor of $n$ and $m$, so $n=kr$ and $m=ks$. Then $$ h=na+mb=kra+ksb=k(ra+sb) $$ proves that $k$ is a divisor of $h$, hence $k\le h$.

Answer 2

Easy direction.

We'll show that $n\mathbb{Z}+m\mathbb{Z} \subseteq \mathrm{hcf}(n,m)\mathbb{Z}$. Since $\mathrm{hcf}(n,m) \mid n,$ hence $$n\mathbb{Z} \subseteq \mathrm{hcf}(n,m)\mathbb{Z}.$$ Similarly $$m\mathbb{Z} \subseteq \mathrm{hcf}(n,m)\mathbb{Z}.$$ So $$n\mathbb{Z}+m\mathbb{Z} \subseteq \mathrm{hcf}(n,m)\mathbb{Z}.$$

(Try to justify all the steps above in your own writeup by formulating them as Lemmas and then proving the Lemmas.)

Hard direction.

We need to show that $\mathrm{hcf}(n,m)\mathbb{Z} \subseteq n\mathbb{Z}+m\mathbb{Z}$.

It suffices to show that $\mathrm{hcf}(n,m) \in n\mathbb{Z}+m\mathbb{Z}$.

(Try to justify this in your own writeup by formulating it as a Lemma and proving it.)

But this is a consequence of Bezout's theorem.

Answer 3

Let $x\in h\mathbb Z$. There exist integers $a$ and $b$ with $ma+nb=h$ (Euclidean algorithm). Now $x=hz$, for $z\in \mathbb Z$. So $x=(ma+nb)z=maz+nbz$. This shows $x\in m\mathbb Z+n\mathbb Z$. Then $h\mathbb Z\subset m\mathbb Z+n\mathbb Z$.

Conversely let$x\in m\mathbb Z+n\mathbb Z$. Then $x=mz_1+nz_2$. But $h|m,n$. Hence $x=hcz_1+hdz_2=h(cz_1+dz_2)$ for some $c,d,z_1,z_2\in \mathbb Z$... Thus $x\in h\mathbb Z$. Thus $m\mathbb Z+n\mathbb Z\subset h\mathbb Z$...

Answer 4

This follows from a well known fact (using the Euclidean algorithm):

Let $m,n\in\mathbb{Z}$ then there exists $x,y\in\mathbb{Z}$ such that $$mx+ny=h$$ where $h=\gcd(m,n)$

It is enough to show that $$h\mathbb{Z}\subseteq m\mathbb{Z}+n\mathbb{Z}\subseteq h\mathbb{Z}$$

• Any element in $h\mathbb{Z}$ is a multiple of $h$, so it must be divisible by $mx+ny$. This means that $h\mathbb{Z}\subseteq m\mathbb{Z}+n\mathbb{Z}$
• Since $m\mathbb{Z}\subseteq h\mathbb{Z}$ and $n\mathbb{Z}\subseteq h\mathbb{Z}$ we must also have that $m\mathbb{Z}+n\mathbb{Z}\subseteq h\mathbb{Z}$

Therefore $$m\mathbb{Z}+n\mathbb{Z}=h\mathbb{Z}$$