elementary number theory - 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.

Answer

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.