BdMO Online Forum

Let $$a_1, ........., a_n$$ be any non-zero integers whose g.c.d is $$d$$. Then there exist integers
$$x_1, ....., x_n$$ such that $$a_1 x_1 ++.....+a_n x_n = d$$.

An approach is to prove the case $n=2$ and then induct.

Let $S=\{a_1x_1+\cdots+a_nx_n:x_1,\dots,x_n\in\mathbb Z\}$. Let $d'$ be the smallest positive element of $S$. Prove the following:

(i) $d$ divides $d'$.

(ii) $d'$ divides $d$.

So $d=d'\in S$ and your conclusion will follow.