ベズーの等式

\(g=0\) のとき, \(x_1=x_2=\ldots=x_n=0\) とすれば良い.

\(g\neq0\) のとき,
\(M=\{a_1x_1+a_2x_2+\cdots+a_nx_n\mid x_1, x_2, \ldots, x_n\in\mathbf{Z}\}\) とおく.
\(x_1=\ldots=x_n=0\) を考えれば \(0\in M\) であり,
ある \(k\) で \(x_k=1\) で他の \(i\) では \(x_i=0\) とすれば \(a_k\in M\) なので, \(a_1,\ldots,a_n\in M\) である.
\(g\neq 0\) より, \(a_i\neq 0\) となる \(i\) が存在するので \(M\neq\{0\}\).
\(x, y\in M\) とすると, 整数 \(x_1,\ldots,x_n,\ y_1,\ldots,y_n\) を用いて \(x=a_1x_1+\cdots+a_nx_n,\ y=a_1y_1+\cdots+a_ny_n\) と書けるが,
\(x-y=a_1(x_1-y_1)+\cdots+a_n(x_n-y_n)\)
は \(x_1-y_1,\ldots,x_n-y_n\) が全て整数であることより, \(x-y\in M\) である.
よって \(M\) は正の整数を含む.
そこで \(M\) に含まれる正の整数のうち最小のものを \(d\) とおく.

任意の \(m\in M\) に対して \(m=dq+r\ (0\leq r<d)\) と整数 \(q, r\) を用いて書ける.
\(d=a_1x_1+\cdots+a_nx_n\) とすると \(dq=a_1(x_1q)+\cdots+a_n(x_nq)\) なので \(dq\in M\).
ゆえに \(r=m-dq\in M\) となるが, \(r\neq 0\) とすると \(d\) の最小性に矛盾する.
したがって \(r=0\) であり, \(m=dq\) より \(d\mid m\) がわかる.

\(a_1,\ldots,a_n\in M\) なので, 任意の \(i\) に対して \(d\mid a_i\) となるが,
最大公約数の定義より, \(d\mid g\) である.
また, 任意の \(i\) に対して \(g\mid a_i\) であるから, 任意の \(m\in M\) に対して \(g\mid m\) である.
よって \(g\mid d\).
以上より \(d=g\) となり命題は示された.

上の証明の中で, 任意の \(m\in M\) に対して \(d\mid m\) であり,
\(d=g=\mathrm{gcd}(a_1, a_2, \ldots, a_n)\) であることよりわかる.