# Let $m \in \mathbb{Z^+} , n \in \mathbb{Z^+}$ and let $d=\gcd(m,n)$. Prove that $m\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}$

Let $m \in \mathbb{Z^+} , n \in \mathbb{Z^+}$ and let $d=\gcd(m,n)$. Prove that $$m\mathbb{Z}+n\mathbb{Z}=d\mathbb{Z}.$$ My attempt is use inclusion to show. Let $a \in m\mathbb{Z}+n\mathbb{Z}$. Then we have $a=ms+nt$. Since $d=\gcd(m,n)$, by Bezout Lemma, we have $d=ms+nt$ for some integers $s$, $n$. Hence, we have $a=ms+nt=d \in d\mathbb{Z}$. Let $a \in d \mathbb{Z}$. Then we have $a=db=msb+ntb \in m\mathbb{Z}+n\mathbb{Z}$. Is my proof valid?

Remark: the following is the part 2 of the question. Prove that $m\mathbb{Z}\cap n\mathbb{Z}=\frac{mn}{d}\mathbb{Z}$. This one I have no idea how to start

-
I don't see why the $s$ and $t$ for $a$ must be the same as those for $d$. For the first direction I think I would consider the fact that $n=pd$ for some $p$, and $m=qd$ for some $q$ (since $d$ is a divisor of both $m$ and $n$) –  Joe Tait Feb 11 '13 at 15:13
To extend @JoeTait's comment, you seem to have proven that $m\mathbb Z+n\mathbb Z$ contains only $d$, which is far from true. –  Thomas Andrews Feb 11 '13 at 15:14
Also, I suspect you mean, "...by Bezout Lemma,... for some integers $s,t$." –  Thomas Andrews Feb 11 '13 at 15:16
In general, the best way to prove two sets, $A,B$, are equal is to prove that if $x\in A$ then $x\in B$, and if $x\in B$ then $x\in A$. –  Thomas Andrews Feb 11 '13 at 15:18

Unfortunately you're not correct, but you're close. You've used $s$ and $t$ in two different situations, where they should not have been used.

What we actually have to do for the first inclusion is, given $a \in m\mathbb{Z}+n\mathbb{Z}$, simply state that $a = xm+yn$. We don't need to apply Bezout's theorem here, only use the fact that $d = \gcd(m,n) \implies d$ divides $m$ and $d$divides $n$. Hence $d$ divides $xm + yn = a$ so $a \in d\mathbb{Z}$ and hence $m\mathbb{Z}+n\mathbb{Z} \subset d\mathbb{Z}$

For the other inclusion, you use Bezout's theorem to state that $d = ms + nt$ for some integers $s,t$ and argue as you have done in the second part, which is correct.

-
then can i prove like this ? Since $d|m$ and $d|n$, we have $m=dk$ and $n=dl$. Hence, $m\mathbb{Z}+n\mathbb{Z}=dk\mathbb{Z}+dl\mathbb{Z}=d\mathbb{Z}$ –  Idonknow Feb 11 '13 at 15:32
@Idonknow I think it's best if you replace the last equals sign with a $\subset$, because for general $k$ and $l$, we only know that $dk\mathbb{Z} + dl\mathbb{Z} \subset d\mathbb{Z}$. We can make the $zsubset$ sign an equals by proving the other direction. We can do this because $k$ and $l$ are coprime, but it is not true for general $k$ and $l$, consider $k=l=2$, for $d$ not equal to 1, certainly $d2\mathbb{Z}+d2\mathbb{Z}$ is not $d\mathbb{Z}$ since the left hand side does not contain $d$. –  Tom Oldfield Feb 11 '13 at 15:44

Hint: You can separate the prove into two different parts that are, imo, easier: First prove that if $m$ is the lowest positive integer in $a\mathbb{Z}$, then $m=a$, then prove that in $m\mathbb{Z}+n\mathbb{Z}$, $d$ is the lowest positive integer. You should find it easier that way.

-

Part $1$ is straightforward if done universally.  Write $\rm\,(a,b)\,$ for $\rm\,gcd(a,b).$ Then

$$\begin{eqnarray} \rm c&\mid&\rm m,\ \ \ n&\iff&\rm\ \ c&\,\mid&\!\rm (m,n)&&\text{by universal definition of gcd}\\ \rm c\Bbb Z &\supseteq&\rm m\,\Bbb Z, n\Bbb Z &\iff&\rm c\Bbb Z&\supseteq&\rm\! (m,n)\Bbb Z\quad &&\rm\text{since}\ j\mid k\iff j\Bbb Z\, \supseteq\, k\Bbb Z\ \ \text{[ divides = contains ]}\\ &&\rm m\Bbb Z + n\Bbb Z &\ \ =&\rm (m\!&,&\!\!\!\rm n)\,\Bbb Z&&\text{by universal definition of sum of subgroups} \end{eqnarray}$$

Above we used that every subgroup of $\rm\,\Bbb Z\,$ is cyclic, say $\rm\,c\Bbb Z,\,$ by Euclid/Bezout.

For part $2$, write $\rm\,lcm(a,b)\,$ as $\rm\,[a,b],$ so $\rm\,a\Bbb Z\cap b\Bbb Z = [a,b]\Bbb Z,\,\:$ i.e. $\rm\: a,b\mid c\iff [a,b]\mid c.\:$ Then

Theorem $\rm\,\ (a,b)\, =\, ab/[a,b]$

Proof $\rm\quad c\,|\:a,b \;\iff\; a,b\:|\:ab/c \;\iff\; [a,b]\:|\:ab/c \;\iff\; c\:|\:ab/[a,b] \quad\;\;$

Therefore $\rm\:(a,b) = ab/[a,b]\:$ by the universal definition of the gcd.

-