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

Question

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.

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

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

Answer 3

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

Since $e\in \{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 $a\in S$ and $b\in S$.