Ytukyg

Let $S = {ax + by: x,y in mathbb{Z}}$ and let $e > 0$ be the smallest element in $S$. Prove that $e mid a$, and hence prove that $e = gcd(a,b)$

I'm afraid I can't provide much of my initial working here because I'm at a loss of how to start.

I suppose that to show $emid a$ I would have to show that $eg = a$ for some $g in mathbb{Z}$. But I have no idea how I would do this.

When I first saw this problem, I was pretty surprised at how the proof went, so I'll just get you started on it.

By the Division Theorem, we have:
$$a=qe+r text{ for } 0 leq r < e$$
Now, we need to show $r=0$. To do this, we can use the fact that $e=ax+by$ for some $x,y in Bbb{Z}$ and that $a=1a+0b$, so:
$$1a+0b=q(ax+by)+r implies a(1-q)-bqy=r$$
Now, combine the fact that $r=au+bv$ for $u,v in Bbb{Z}$ and that $0 leq r < e$ to prove $r=0$.

Here is one conceptual way to present a proof of Bezout's Identity for the gcd. The set $rm,S,$ of integers of the form $rm,a x + b y, x,yin mathbb Z,,$ is closed under subtraction hence, by the Lemma, every positive $rm,kin S,$ is divisible by $rm,d = $ least positive $rmin S.,$ Therefore $rm,a,bin S$ $,Rightarrow,$ $rm dmid a,b,,$ i.e. $rm,d,$ is a common divisor of $rm,a,b,,$ the greatest by $rm cmid a,b,$ $Rightarrow$ $rm,cmid d = ax+by$ $Rightarrow$ $rm,cle d$

Lemma $ $ Let $,rm Sneemptyset ,$ be a set of integers $>0,$ closed under subtraction $> 0,,$ i.e. for all $rm,n,min S, ,$ $rm n > m Rightarrow n-m, in, S.,$ Then the least $rm:ellin S,$ divides every element of $,rm S.$

Proof ${bf 1}, $ If not there is a least nonmultiple $rm,nin S,,$ contra $rm,n-ell in S,$ is a nonmultiple of $rm,ell.$

Proof ${bf 2},rm, S,$ closed under subtraction $rm,Rightarrow,S,$ closed under remainder (mod), when it is $ne 0,$ since mod is simply repeated subtraction, i.e. $rm a mod b, =, a - k b, =, a!-!b!-!b!-cdots! -!b.,$ Thus $rm,nin S,$ $Rightarrow$ $rm, (n mod ell) = 0,,$ else it is in $,rm S,$ and smaller than $rm,ell,,$ contra minimality of $rm,ell.$

Remark $ $ In a nutshell, two applications of induction yield the following inferences

$ rmbegin{eqnarray} S closed under {bf subtraction} &:Rightarrow:&rm S closed under {bf mod} = remainder = repeated subtraction \
&:Rightarrow:&rm S closed under {bf gcd} = repeated mod (Euclid's algorithm) end{eqnarray}$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd.

The conceptual structure will be clarified when one studies ideals of rings, where the above proof generalizes to show that Euclidean domains are PIDs.

One must define $e$ as the smallest positive element of $S$.

Since $ein {ax + by: x,y in mathbb{Z}}$, there are some numbers $x_1,y_1$ such that $e = ax_1+by_1$.

Suppose some positive member $f$ of $S = {ax + by: x,y in mathbb{Z}}$ were not a multiple of $e$. Then we have some numbers $x_2,y_2$ such that $f = ax_2+by_2$.

Since $e$ is the smallest, we must have $e<f$. Let $r$ be the remainder when $f$ is divided by $e$. Then using the relations
begin{align}
f & = ax_2 + by_2 \
e & = ax_1 + by_1
end{align}
you can show that $r in S$. But $0<r$ since $f$ is not a multiple of $e$ and $r<e$ since $r$ was a remainder upon division by $e$.

That means there is a positive member of $S$, namely $r$ that is smaller than $e$. That can't happen since $e$ is the smallest.

Hence every member of $S$ is a multiple of $e$. Therefore $e$ is a common divisor of $ain S$ and $bin S$.