# Show $GCD(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$

Given $a_1, a_2, a_3, \ldots , a_n$ not all zero, show $\gcd(a_1, a_2, a_3, \ldots , a_n)$ is the least positive integer that can be expressed in the form $a_1x_1+a_2x_2+ \ldots +a_nx_n$. Also deduce $a_1x_1+a_2x_2+ \ldots +a_nx_n = b$ has solutions $\iff \gcd(a_1, a_2, a_3, \ldots , a_n)|b$.

I know that $ax+by=n$ has integer solutions $\iff \gcd(a,b)|n$. I'll need to use induction to show $a_1x_1+a_2x_2+ \ldots +a_nx_n = \gcd(a_1, a_2, a_3, \ldots , a_n)$ has solutions, and then I will be able to say that as $\gcd(a_1, a_2, a_3, \ldots , a_n) | a_1x_1+a_2x_2+ \ldots +a_nx_n$ for any $x_1,x_2, x_3 \ldots x_n$ then $c \leq \gcd(a_1, a_2, a_3, \ldots , a_n)$ and $c \geq \gcd(a_1, a_2, a_3, \ldots , a_n)$, and thus $c=\gcd(a_1, a_2, a_3, \ldots , a_n)$.

• are you familiar with general algebra? – mookid Mar 19 '14 at 20:25
• I know the basics of general algebra – flamingohats Mar 19 '14 at 20:29

Here is a conceptual way to prove Bezout's Identity for the gcd. The set $\rm\,S\,$ of integers of form $\rm\,a_1\,x_1 + \cdots + a_n x_n,\ x_i\in \mathbb Z\,$ is $\rm\color{#c00}{closed\ under\ subtraction}$ so, by the Lemma below, every positive $\rm\,k\in S\,$ is divisible by $\rm\,d :=$ least positive $\rm\in S.\,$ Therefore $\rm\,a_i\in S$ $\,\Rightarrow\,$ $\rm d\mid a_i,\,$ i.e. $\rm\,d\,$ is a common divisor of all $\rm\,a_i,\,$ necessarily greatest by $\rm\ c\mid \color{#0a0}{a_{\,i}}$ $\Rightarrow$ $\rm\,c\mid d = \color{#0a0}{a_{\,1}}\,x_1\!+\!\cdots\!+\!\color{#0a0}{a_{\,n}}\,x_n$ $\Rightarrow$ $\rm\,c\le d$

Lemma $\ \$ Let $\,\rm S\ne\emptyset \,$ be a set of integers $>0\,$ $\rm\color{#c00}{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.\,$ Therefore $\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 applications of induction yield the following inferences

$\rm\begin{eqnarray}\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) \end{eqnarray}$

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

• Very nice answer as usual. One doubt: why does $c \mid a,b$ imply $c \mid d$? Is it because we can always write $d = ya + zb$ for some $y, z \in \mathbb{Z}$? – Anant May 12 '14 at 9:06
• @Anant $\,\ c\mid a_i\,$ so $\,c\mid a_i x_i,\,$ so $\ c\mid a_1x_1 +\cdots + a_n x_n,\,$ i.e. the set of multiples of $\,c\,$ are closed under addition and interger multiples $\, x\to kx,\ k\in\Bbb Z,\,$ i.e. they form an ideal (note: I fixed one sentence that I overlooked converting from the binary to $n$-ary case). – Bill Dubuque May 12 '14 at 13:22
• Clear now, thanks! – Anant May 12 '14 at 13:32

Outline: The induction step goes as follows. Suppose that for a particular integer $k$, and integers $a_1,\dots,a_k$, there exist integers $x_1,x_2,\dots,x_k$ such that $$\gcd(a_1,a_2,\dots,a_k)=x_1a_1+\cdots+x_ka_k.\tag{1}$$ We want to show that there exist integers $y_1,\dots,y_k,y_{k+1}$ such that $$\gcd(a_1,\dots,a_k,a_{k+1})=y_1a_1+\cdots+y_ka_k+y_{k+1}a_{k+1}.$$

We need the fact that $$\gcd(a_1,a_2,\dots,a_k,a_{k+1})=\gcd(\gcd(a_1,a_2,\dots,a_k),a_{k+1}).$$ This is not particularly hard to prove.

So by a familiar result, there exist integers $s$ and $t$ such that $$\gcd(a_1,\dots,a_k,a_{k+1})=s\gcd(a_1,\dots,a_k)+ta_{k+1}.\tag{2}$$ Substitute the right-hand side of (1) for $\gcd(a_1,a_2,\dots,a_k)$ in (2).

After we have proved this representation theorem, the rest is straightforward. Since the gcd $d$ of $a_1,a_2,\dots,a_n$ is representable, every integer multiple of $d$ is representable. The converse is clear, any representable number is a multiple of $d$.

The subgroup of $\Bbb Z$, $a_1\Bbb Z + \cdots + a_n\Bbb Z$ has the form $d\Bbb Z$. $d$ is the least positive integer that can be expressed in the form you look for.

Now write $$d = a_1 x_1 + \cdots + a_n x_n$$ and divide by $\gcd(a_1,\dots,a_n)$; this shows that $$\gcd(a_1,\dots,a_n) |d$$ Then, the Bezout identity and an induction prove that $$\gcd(a_1,\dots,a_n) \in a_1\Bbb Z + \cdots + a_n\Bbb Z = d\Bbb Z$$

that is, $d|\gcd(a_1,\dots,a_n)$. Eventually, $$d= \gcd(a_1,\dots,a_n)$$