Vtgyjfy

I have the following problem:

Let $a, b inmathbb{Z}$. Show that $,{ ax + by : x, y in mathbb{Z}} = { n gcd(a,b) : nin 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, $ ngcd(a,b) = n(aj+bk),$ $Rightarrow$ $,gcd(a,b),Bbb Zsubseteq aBbb Z+bBbb Z., $ Conversely,

$,gcd(a,b)mid a,b,Rightarrow,gcd(a,b)mid ax!+!by,,$ so $,ax!+!by = ngcd(a,b),,$ so $,a,Bbb Z+b,Bbb Zsubseteq gcd(a,b)Bbb Z$

Or we can induct. $ $ wlog $,a,b> 0,$ by $,-aBbb Z = aBbb 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!: aBbb Z + aBbb Z = aBbb Z.,$ Else $,aneq b.,$ By symmetry, wlog $,a>b.,$ $,aBbb Z+bBbb Z = color{#0a0}{(a!-!b)Bbb Z+bBbb 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 $rmcolor{}{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 $$ngcd(a,b)=ax_0+by_0$$

Thus we have shown all values of $k$ must be of the form $ngcd(a,b)$ and that for every $ngcd(a,b)$ with $nin 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+bymid x,yinmathbb Z}subseteq {n(a,b)mid ninmathbb Z}$.

Now prove $exists x,yinmathbb Z$ such that $n(a,b)=ax+by$.$ (2)$

Euclid's algorithm shows that $exists x_0,y_0inmathbb Z ((a,b)=ax_0+by_0)$. Use this to show $(2)$.

This concludes that ${n(a,b)mid ninmathbb Z}subseteq{ax+bymid x,yinmathbb Z}$.