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