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.
 A: Hint: $\gcd (a_1,a_2,\dots,a_n) = \gcd\bigl(a_1,\gcd(a_2,\dots,a_n)\bigr)$.
A: 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$.
A: 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.
A: 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?
