Show $a\Bbb Z+b\Bbb Z = \gcd(a,b)\Bbb Z$ I have the following problem:
Let $a, b \in\mathbb{Z}$. Show that $\,\{ ax + by\ :\ x, y \in \mathbb{Z}\} = \{ n \gcd(a,b)\ :\ n\in \mathbb{Z} \}$ 
I understand that the Bezout's lemma says that $gcd(a,b) = ax +by$, so Im not really how you would go about proving the above, it doesn't really make sense to me. Any help is appreciated1
 A: Bezout's lemma says that there is a solution for every pair of natural numbers $(a,b)$ to the linear Diophantine equation: $$\gcd(a,b)=ax+by$$
Now define $k=ax+by$
And let $(x,y)$ run over the integers.
We have $\gcd(a,b)\mid k$ because it divides the right hand side.
Thus $k$ must be an integer multiple of $\gcd(a,b)$. 
But by Bezout's lemma we know there is a solution $(x_0,y_0)=(nx,yx)$ to $$n\gcd(a,b)=ax_0+by_0$$
Thus we have shown all values of $k$ must be of the form $n\gcd(a,b)$ and that for every $n\gcd(a,b)$ with $n\in \mathbb{Z}$ there exists integers $(x_0,y_0)$ satisfying the linear equation. Which completes the proof.
A: To prove equality of two sets, you need to show that each is contained in the other.
$\{ax+by | x,y \in \Bbb Z\} \subset \{n \gcd(a,b) | n \in \Bbb Z\}$, because for a given element of the former $ax+by$, we can take $n=\frac{a}{\gcd(a,b)}x+\frac{b}{\gcd(a,b)}y$ to see that it is an element of the latter set. 
Now as you pointed out there exists a pair of integers $x,y$ such that $ax+by = \gcd(a,b)$. Can you use this to show that $\{n \gcd(a,b) | n \in \Bbb Z\} \subset \{ax+by | x,y \in \Bbb Z\}$?
A: By Bezout, for some $\,i,j\in\Bbb Z\!:$ $\ \gcd(a,b) = aj\!+\!bk\,$ $\Rightarrow$ $\,\gcd(a,b)\,\Bbb Z\subseteq  a\Bbb Z+b\Bbb Z.\, $ Reversely,
$\,\gcd(a,b)\mid a,b\,\Rightarrow\,\gcd(a,b)\mid ax\!+\!by,\,$ so $\,ax\!+\!by = n\gcd(a,b),\,$ so $\,a\,\Bbb Z+b\,\Bbb Z\subseteq \gcd(a,b)\Bbb Z$

Or we can induct. $ $  wlog $\,a,b> 0\,$ by $\,-a\Bbb Z = a\Bbb Z,\, (\pm a,\pm b) = (a,b),\,$ and it is true if $\,a\,$ or $\,b=0.$
Proof by induction on $\,\color{#90f}{{\rm size} := a+b}.\,$ True if $\,a = b\!:\ a\Bbb Z + a\Bbb Z = a\Bbb Z.\,$ Else $\,a\neq b.\,$ By symmetry, wlog $\,a>b.\,$ $\,a\Bbb Z+b\Bbb Z = \color{#0a0}{(a\!-\!b)\Bbb Z+b\Bbb Z} = (a\!-\!b,b)\Bbb Z = (a,b)\Bbb Z\,$ because the  $\,\color{#0a0}{\rm green}\,$ instance has smaller $\,\color{#90f}{{\rm size}} = (a\!-\!b)+b = a < \color{#90f}{a+b},\,$ so $\rm\color{}{induction}\,$ applies. $\ $ QED
A: Let $k = \text{gcd}(a, b)$
Then $ax + by = k(\frac{a}{k} x + \frac{b}{k} y)$
Then since $x, y, \frac{a}{k}, \frac{b}{k}$ are all integers, so is the entire expression, which is $n$.
A: Trivially $(a,b)\mid ax+by$ (since $(a,b)\mid a$ and $(a,b)\mid b$).  
This shows $\{ax+by\mid x,y\in\mathbb Z\}\subseteq \{n(a,b)\mid n\in\mathbb Z\}$.  

Now prove $\exists x,y\in\mathbb Z$ such that $n(a,b)=ax+by$.$\ \ \ (2)$  
Euclid's algorithm shows that $\exists x_0,y_0\in\mathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.  
This concludes that $\{n(a,b)\mid n\in\mathbb Z\}\subseteq\{ax+by\mid x,y\in\mathbb Z\}$.
