Show $a\Bbb Z+b\Bbb Z = \gcd(a,b)\Bbb Z$

Question

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 1

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

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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