elementary number theory - Show $aBbb Z+bBbb 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

Answer

By Bezout, for some $\,i,j\in\Bbb Z\!:$ $\ n\gcd(a,b) = n(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