# 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

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

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.

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\}$?

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$.

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\}$.