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$

Question

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

Answer 1

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

Answer 2

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

Answer 3

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