# Help with a proof - gcd

Printable View

• Nov 2nd 2013, 02:19 AM
Stormey
Help with a proof - gcd
We define $a\mathbb{Z}+b\mathbb{Z}=\left \{ au+bv:u,v\in\mathbb{Z} \right \}$.

I need to prove that $a\mathbb{Z}+b\mathbb{Z}=(a,b)\cdot\mathbb{Z}$.

so, I need to prove $a\mathbb{Z}+b\mathbb{Z}\subseteq (a,b)\cdot\mathbb{Z}$ and $a\mathbb{Z}+b\mathbb{Z}\supseteq (a,b)\cdot\mathbb{Z}$.

One direction is easy:

( $\supseteq$) Let $n\in (a,b)\cdot\mathbb{Z}$, so $n=(a,b)\cdot k$, for some $k\in\mathbb{Z}$, and since there exist $s,t\in\mathbb{Z}$ such that $(a,b)=sa+tb$, we get:
$n=(a,b)\cdot k$
$n=(sa+tb)k$
$n=ska+tkb$
$n=(sk)a+(tk)b \Rightarrow n\in a\mathbb{Z}+b\mathbb{Z}$

( $\subseteq$)
I need help here...

Thanks in advanced!
• Nov 2nd 2013, 03:17 AM
emakarov
Re: Help with a proof - gcd
The ⊆ direction is easier: it does not even need Bézout's identity (a, b) = sa + tb.
• Nov 2nd 2013, 08:52 AM
Stormey
Re: Help with a proof - gcd
Sorry, I couldn't think of anything.
Can you give me another hint?
• Nov 2nd 2013, 09:01 AM
johng
Re: Help with a proof - gcd
$a=(a,b)a_1$ and $b=(a,b)b_1$ with $a_1,b_1\in\mathbb{Z}$