Smallest positive element of $ \{ax + by: x,y \in \mathbb{Z}\}$ is $\gcd(a,b)$ [duplicate]

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 $e\mid 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.

Solution 1:

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-qx)-bqy=r$$ Now we can combine the fact that $r=au+bv$ for $u,v \in \Bbb{Z}$ and that $0 \leq r < e$ to prove $r=0$.

Solution 2:

Here is a conceptual way to prove Bezout's Identity for the gcd. The set $\rm\,S\,$ of integers of the form $\rm\,a x + b y,\ x,y\in \mathbb Z,\,$ is closed under subtraction so, by the Lemma below, every positive $\rm\,k\in S\,$ is divisible by $\rm\,d = $ least positive $\rm\in S.\,$ So $\rm\,a,b\in S$ $\,\Rightarrow\,$ $\rm d\mid a,b,\,$ i.e. $\rm\,d\,$ is a common divisor of $\rm\,a,b,\,$ necessarily the greatest such by $\rm\ c\mid a,b\,$ $\Rightarrow$ $\rm\,c\mid d = ax+by$ $\Rightarrow$ $\rm\,c\le d$.

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

Proof ${\bf\ 1}\,\ $ If not there is a least nonmultiple $\rm\,n\in 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\,n\in 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 inductions yield

$\rm 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)$

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