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

Question

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 Bézout's 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

Answer 1

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 Bézout's identity 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 Bézout's identity to state that $d = ms + nt$ for some integers $s,t$ and argue as you have done in the second part, which is correct.

Answer 2

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.

Answer 3

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.