Euclidの互除法と帰納法で証明しても良いし、
どっちかというとそっちのほうが計算的だけどもっと簡単に証明。

gcm(a_1, a_2, ........., a_n) = d である。
a_{1}x_{1} + ......... + a_{n}x_{n}と表せる形の整数の集合 I を考える。
I = { x ∈ Z : 或る x_{1}, ........, x_{n} が存在して n = a_{1}x_{1} + ......... + a_{n}x_{n} }
x ∈ I ならば x の倍数 nx も I の要素であり、またx, y ∈ I ならば x ± y ∈ I となる。
よって I の要素の絶対値のうち最小のものを e とすると I は e の倍数の集合となることがわかる。
（∵ e' = ne + e'' , 0 ＜ e'' ＜ e とすると e'' ∈ I となり矛盾する。）
或る x_1, ........, x_n が存在して e = a_1x_1 + ......... + a_nx_n だから e は d の倍数。
また a_i は I に含まれるので、逆に a_i は e の倍数。よって e は a_1, ........., a_n の公約数。
よって e = d。つまり d は a_{1}x_{1} + ......... + a_{n}x_{n} の形に表すことが出来る。
quod erat demonstrandum.

と、ここまで解いてリロードしたら>>575が既に解いてた。
でも「a_1/d,a_2/dはそれぞれ互いに素であるから、 a_1/d*x_1+a_2/d*x_2=1が成り立つ。」
これ使って良いのかな。