Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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, " 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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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