# Thread: Help with a proof - gcd

1. ## Help with a proof - gcd

We define $\displaystyle a\mathbb{Z}+b\mathbb{Z}=\left \{ au+bv:u,v\in\mathbb{Z} \right \}$.

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

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

One direction is easy:

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

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

2. ## Re: Help with a proof - gcd

The ⊆ direction is easier: it does not even need Bézout's identity (a, b) = sa + tb.

3. ## Re: Help with a proof - gcd

Sorry, I couldn't think of anything.
Can you give me another hint?

4. ## Re: Help with a proof - gcd

$\displaystyle a=(a,b)a_1$ and $\displaystyle b=(a,b)b_1$ with $\displaystyle a_1,b_1\in\mathbb{Z}$