Euclidの互除法とBezoutの補題

$a_{n+1}=0$ となる $n$ が存在しないと仮定すると
$$b=a_1>a_2>\cdots \geq 0$$
より、$0\leq a_{b+2}\leq b+1-(b+2)<0$ となり、矛盾するから、$a_{n+1}=0$ となる $n$ は必ず存在する。

そこでそのような最小の $n$ を $s$ とおくと $a_{s-1}=q_s a_s$ より $a_s\mid a_{s-1}$ となる。
$1\leq k\leq s$ かつ $a_s\mid a_k, a_{k+1}, \ldots, a_s$ とすると $a_{k-1}=q_k a_k+a_{k+1}$ も $a_s$ の倍数だから数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $a_s$ の倍数となる。とくに $a_s$ は $a, b$ の公約数である。

一方、$a_0=a, a_1=b$ は $\gcd(a_0, a_1)=\gcd(a, b)$ で割り切れる。
$a_0, a_1, \ldots, a_k$ が $\gcd(a, b)$ で割り切れるとき
$a_{k+1}=a_{k-1}-q_k a_k$ も $\gcd(a, b)$ で割り切れる。
よって 数学的帰納法より $a=a_0, b=a_1, \ldots, a_s$ はすべて $\gcd(a, b)$ の倍数となる。とくに $a_s$ は $\gcd(a, b)$ の倍数である。

以上のことより $a_s=\gcd(a, b)$ となる。

$d=\gcd(a_1, a_2, \ldots, a_k), a_i=d b_i$ とおく。
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$
となる整数 $x_1, x_2, \ldots, x_k$ が存在するとき、
$$n=d(b_1 x_1+b_2 x_2+\cdots +b_k x_k)$$
より $n$ は $d=\gcd(a_1, a_2, \ldots, a_k)$ の倍数である。

$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=m, a_1 y_1+a_2 y_2+\cdots +a_k y_k=n$$
となる整数 $x_1, x_2, \ldots, x_k, y_1, y_2, \ldots, y_k$ が存在するとき、任意の整数 $s, t$ について
$$a_1 (sx_1+ty_1)+a_2 (sx_2+ty_2)+\cdots +a_k (sx_k+ty_k)=sm+tn$$
となるから、
$$a_1 z_1+a_2 z_2+\cdots a_k z_k=sm+tn$$
となる $z_1, z_2, \ldots, z_k$ がとれる。よって 倍数と約数:定理4 より
$$a_1 x_1+a_2 x_2+\cdots +a_k x_k=n$$
となる整数 $x_1, x_2, \ldots, x_k$ が存在するような最小の正の $n$ を $n_0$ とおくと
$$\exists x_1, x_2, \ldots, x_k \in \Z [a_1 x_1+a_2 x_2+\cdots +a_k x_k=n]\Longleftrightarrow n_0 \mid n$$
となる。
$x_i=1, x_j=0 (j\neq i)$ のとき $a_1 x_1+a_2 x_2+\cdots +a_k x_k=a_i$ となるから、$n_0$ は $a_1, a_2, \ldots, a_k$ の公約数である。しかし先に示したことから
$n_0$ は $\gcd(a_1, a_2, \ldots, a_k)$ の倍数なので $n_0=\gcd(a_1, a_2, \ldots, a_k)$.