1
$\begingroup$

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

$\endgroup$
3
1
$\begingroup$

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

$\endgroup$
1
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.