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 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
 A: 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.
A: 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.
A: 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.
A: Well firstly, how do you define $\gcd(a,b)$? I'll define it by the converse of a proposition in Artin Algebra (Prop 2.3.5)



Namely, we'll prove

Converse of Prop 2.3.5: Let $a$ and $b$ be integers not both zero. Suppose (a) $d$ divides $a$ and $b$, (b) any integer $e$ that divides $a$ and $b$ also divides $d$ and (c) there are integers $r$ and $s$ s.t. $d=ra+sb$. Then $\mathbb Z d=\mathbb Z a + \mathbb Z b$.

where $d:=\gcd(a,b)$ is defined by the integer given by the assumptions of the above stated Converse of Prop 2.3.5.
-
Pf:
($\supseteq$)
Let $n \in \mathbb Za + \mathbb Zb$. Then there are integers $n_a, n_b$ s.t. $n=n_a a + n_b b$. We must show $n \in \mathbb Zd$, i.e. we must find an integer $n_d$ s.t. $n=n_d d$.
By $(a)$, there are integers $d_a, d_b$ s.t. $d_a d = a, d_b d = b$. Thus, $$n=n_a a + n_b b = n=n_a d_a d + n_b d_b d.$$
Thus, $n_d = n_a d_a + n_b d_b$.
($\subseteq$)
Let $n \in \mathbb Zd$. Then there is an integer $n_d$ s.t. $n=n_d d$. We must show $n \in \mathbb Za + \mathbb Zb$, i.e. we must find integers $n_a, n_b$ s.t. $n=n_a a + n_b b$.
By $(c)$, there are integers $d_1, d_2$ s.t. $d=d_1 a + d_2 b$. Thus, $$n=n_d d = d_1 a n_d + d_2 b n_d$$
Thus, $n_a = d_1 n_d, n_b = d_2 n_d$.
QED
Note: Observe the original $(c)$ is Bézout's identity, while using $(c)$ as an assumption is no longer Bézout's identity but simply that $d$ has such integer combination form.
Update: A proof without using $(c)$: https://math.stackexchange.com/a/2900969
