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

  • $\begingroup$ are you familiar with general algebra? $\endgroup$ – mookid Mar 19 '14 at 20:25
  • $\begingroup$ I know the basics of general algebra $\endgroup$ – 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.

  • $\begingroup$ 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}$? $\endgroup$ – Anant May 12 '14 at 9:06
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque May 12 '14 at 13:22
  • $\begingroup$ Clear now, thanks! $\endgroup$ – 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) $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.