Question about the Euclidean algorithm with multiple integers

I have tried to do this proof for the whole day, but I still have no idea how to prove it.

Here's the question:

Let $a_1, a_2, \dots , a_k$ be integers with $\gcd(a_1, a_2, \dots , a_k) = 1$, i.e., the largest positive integer dividing all of $a_1, \dots , a_k$ is $1$.

Prove that the equation $$a_1u_1 + a_2u_2 + \dots + a_ku_k = 1$$ has a solution in integers $u_1, u_2, \dots , u_k$.

(Hint. Repeatedly apply the extended Euclidean algorithm. You may find it easier to prove a more general statement in which $\gcd(a_1, \dots , a_k)$ is allowed to be larger than $1$.)

Thanks a lot.

• Do you understand the proof when there are only two numbers? (i.e., when $k=2$?) – Théophile Sep 8 '13 at 0:41
• Not really, it looks so complicated. – leeha Sep 8 '13 at 0:58

Let $d$ be the smallest positive integer representable as $a_1u_1+a_2u_2+\cdots +a_nu_n$. Suppose that $d\gt1$, and let $p$ be a prime dividing $d$. Let's write $d=p\delta$. What we have so far is

$$a_1u_1+a_2u_2+\cdots+ a_nu_n=p\delta$$

By the assumption that $\gcd(a_1,a_2,\ldots a_n)=1$, there is an $a_i$ not divisible by $p$. Without loss of generality (or by relabeling the $a$'s), let's assume that it's $a_1$ that's not divisible by $p$. This means $a_1x+py=1$ has a solution (from the usual Euclidean algorithm). Multiplying both sides of this by $\delta$ makes this $a_1x\delta+p\delta y=\delta$. But we can write this out as

$$a_1(x\delta+u_1y)+a_2(u_2y)+\cdots+ a_n(u_ny)=\delta$$

where $\delta=d/p\lt d$, which contradicts the assumption that $d$ is the smallest positive integer representable as a linear combination of the $a_i$'s. Thus we must have $d=1$.

Added later: I wasn't particularly satisfied with assuming the $n=2$ case of what was to be proved. It finally dawned on me the proof is just as easy if you don't. Instead of writing $a_1x+py=1$, note simply that if $p$ doesn't divide $a_1$, then we can certainly write

$$a_1-pk=r\text{ with } 0\lt r\lt p$$

Both inequalities are important: We need the remainder $r$ to be positive as well as less than $p$. Multiplying both sides of this by $\delta$ gives something that can be written out as

$$a_1(\delta-ku_1)-a_2(ku_2)-\cdots-a_n(ku_n)=r\delta\lt p\delta=d$$

which gives the same contradiction as before.

Hint: $\gcd (a_1,a_2,\dots,a_n) = \gcd\bigl(a_1,\gcd(a_2,\dots,a_n)\bigr)$.

• Indeed, the gcd is uniquely characterized by the condition that $d$ divides $\text{gcd}(a_1, \ldots, a_n)$ iff $d$ divides every $a_i$; the hint follows immediately from this. (In fancier language, the gcd is the infimum in the lattice $\mathbb{N}$ ordered by divisibility.) – user43208 Sep 8 '13 at 12:45

We prove by induction on $n$ that if $n\ge 2$ and $\gcd(a_1,a_2,\dots,a_n)=d_n$ then there exist integers $x_1,x_2,\dots,x_n$ such that $a_1x_1+a_2x_2+\cdots+a_n x_n=d_n$.

The case $n=2$ is a standard theorem. It is nowadays often called Bézout's Identity, or Bézout's Lemma.

It remains to take care of the induction step. Suppose the result is true for $n=k$. We show the result is true for $n=k+1$.

Let $d_{k+1}=\gcd(x_1,x_2, \dots, x_k,x_{k+1})$ and let $d_k=\gcd(a_1,a_2,\dots,a_k)$. Then $d_{k+1}=\gcd(d_k,a_{k+1})$. (You will have to prove this part, it it has not been done in the course.)

By the induction hypothesis, there are integers $w_1,w_2, \dots, w_k$ such that $a_1w_1+a_2w_2+\cdots+a_kw_k=d_k$.

By the case $n=2$, there exist integers $x$ and $y$ such that $d_k x+a_{k+1} y=d_{k+1}$. Thus $$(a_1w_1+a_2w_2+\cdots +a_kw_k)x +a_{k+1}y=d_{k+1}.$$ This gives the desired result for $k+1$, if we take $x_i=w_ix$ for $i=1$ to $k$, and $x_{k+1}=y$.

This is simply a case of Bezout's lemma extended to $n$ variables. I will give a proof in 2 variables-- you should easily be able to extend the argument to $n$ variables.

Consider the set $S= \{ax+by \in \mathbb{N} \mid x, y \in \mathbb{Z} \}$. This set is evidently non-empty, is a subset of $\mathbb{N}$ and so by the well-ordering principle it must have a least element. Let this least element be $d$. Thus $\exists x, y \in \mathbb{Z}$ such that $d=ax+by$.

$\mathbb{Z}$ has a division algorithm, namely that for $m, n \in \mathbb{Z}, \exists! q,r$ st $m = nq+r, 0 \le r < n$. (This is a formal statement of something commonly expressed in fourth grade mathematics, so I will not prove it.) By this token,

$\exists q, r$ st $a=dq+r \Rightarrow a=(ax+by)q +r \Rightarrow r= a-q(ax+by)$

$= a- qax -qby$

$= a(1-qx) + b(-qy)$

This would indicate that $r \in S$. This would contradict our WOP assumption of $d$ being the least element in $S$, unless $r=0$. Thus $r=0 \Rightarrow a=dq \Rightarrow d \mid a$. Using the exact same argument on $b$, we see $d \mid b$.

So we know now that $d$ is a common divisor of $a$ and $b$. To show that $d=(a,b)$, we must show that all other common divisors of $a$ and $b$ divide $d$.

Consider an arbitrary common divisor of $a$ and $b$, $d_0$. $d_0\mid a$, $d_0 \mid b$; thus $\exists \alpha_1, \alpha_2 \in \mathbb{Z}$ st $d_0\alpha_1 =a$, $d_0\alpha_2=b$.

$d_0\alpha_1 =a \Rightarrow d_0\alpha_1x = ax$ $d_0\alpha_2 =b \Rightarrow d_0\alpha_2y = by$

$\rightarrow d_0\alpha_1x + d_0\alpha_2y = ax+by \Rightarrow d_0(\alpha_1x+\alpha_2y) = ax+by=d \Rightarrow$ $d_0 \mid d$ .

Thus our theorem is proven in 2 variables. The argument can be extended very easily to n variables. Do you see how?

• Just curious, do you sometimes go by other names? ;-) – Barry Cipra Sep 14 '13 at 19:09
• Of course- Pessoa is a late Potuguese writer whose work I very much admire, and whose first name I have thus used as a pen name many times now. I am an undergraduate student by the name of Andy. – Fernando Pessoa Sep 16 '13 at 20:50
• I like Pessoa's work as well (though I only know it in translation). – Barry Cipra Sep 16 '13 at 22:05
• As do I. I sadly do not know Portuguese in the slightest. – Fernando Pessoa Sep 18 '13 at 2:06