# 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

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

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_j\in \mathbb Z\,$$ is $$\rm\color{#c00}{closed\ under\ subtraction}$$ so, by the Lemma below, every positive $$\rm\,s\in S\,$$ is divisible by $$\rm\,d :=$$ least positive $$\rm\in S.\,$$ Therefore $$\rm\,a_j\in S$$ $$\,\Rightarrow\,$$ $$\rm d\mid a_j,\,$$ i.e. $$\rm\,d\,$$ is a common divisor of all $$\rm\,a_j,\,$$ necessarily greatest by $$\rm\ c\mid \color{#0a0}{a_{\,j}}$$ $$\Rightarrow$$ $$\rm\,c\mid d = \color{#0a0}{a_{\,1}}\,{\it x_1}\!+\!\cdots\!+\!\color{#0a0}{a_{\,n}}\,{\it x_n}$$ $$\Rightarrow$$ $$\rm\,c\le d.\,$$

Note $$\rm \ s\in S\,\Rightarrow\, d\mid s\,$$ means $$\rm \, S\subseteq d\Bbb Z.\,$$ Reversely $$\rm\,S\supseteq d\Bbb Z\,$$ by $$\rm\,d\in S\,$$ and $$\,\rm S\,$$ closed under integer scalings: $$\rm\ k \sum a_j x_j = \sum a_j (k x_j)\in S.\,$$ Therefore: $$\rm\, S = d\Bbb Z,\,$$ i.e.

$$\rm\bbox[6px,border:1px solid #c00]{ a_1 \Bbb Z +\cdots+a_n \Bbb Z\, =\, \gcd(a_1,\ldots,a_n)\Bbb Z}\qquad$$

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. Namely,  starting from the two elements of $$\rm\,S\,$$ that we know: $$\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\,$$ we search for the least element of $$\rm\,S\,$$ by repeatedly subtracting elements of $$\,\rm S\,$$ to produce smaller elements of $$\rm\,S\,$$ (while keeping track of each elements linear representation in terms of $$\rm\,a\,$$ and $$\rm\,b).\:$$ This is essentially the subtractive form of the Euclidean GCD algorithm (vs. the mod / remainder form), where each reduction / descent step employs subtraction (vs. iterated subtraction = mod).

The underlying algebraic structure of $$\rm\,S\,$$ (closure under addition and scalings) is clarified conceptually on study of ideals of rings, where the above proof (in remainder vs. subtractive form) generalizes to show that Euclidean domains are PIDs.

Beware that this linear representation of the the gcd need not hold true in all domains where gcds exist, e.g. in the UFD $$\rm\:D = \mathbb Q[x,y]\:$$ of polynomials in $$\rm\:x,y\:$$ with rational coefficients we have $$\rm\:gcd(x,y) = 1\:$$ but there are no $$\rm\:f(x,y),\: g(x,y)\in D\:$$ such that $$\rm\:x\:f(x,y) + y\:g(x,y) = 1;\:$$ indeed, if so, then evaluating at $$\rm\:x = 0 = y\:$$ yields $$\:0 = 1.$$

• 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

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