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.

  • $\begingroup$ Do you understand the proof when there are only two numbers? (i.e., when $k=2$?) $\endgroup$ – Théophile Sep 8 '13 at 0:41
  • $\begingroup$ Not really, it looks so complicated. $\endgroup$ – 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)$.

  • $\begingroup$ 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.) $\endgroup$ – 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?

  • $\begingroup$ Just curious, do you sometimes go by other names? ;-) $\endgroup$ – Barry Cipra Sep 14 '13 at 19:09
  • $\begingroup$ 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. $\endgroup$ – Fernando Pessoa Sep 16 '13 at 20:50
  • $\begingroup$ I like Pessoa's work as well (though I only know it in translation). $\endgroup$ – Barry Cipra Sep 16 '13 at 22:05
  • $\begingroup$ As do I. I sadly do not know Portuguese in the slightest. $\endgroup$ – Fernando Pessoa Sep 18 '13 at 2:06

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.