整数に対するベズーの恒等式
$a,b\in\mathbb Z$ は同時に 0 ではないとし、
\[g=\gcd(|a|,|b|)>0\]とおく。このとき、次の等式を満たす整数 $x,y$ が存在する。
\[ax+by=g.\]さらに、$a,b$ のすべての整数線形結合からなる集合は、ちょうど $g$ の倍数全体である。
\[\{ax+by:x,y\in\mathbb Z\}=g\mathbb Z=\{ng:n\in\mathbb Z\}.\]この記事で証明するのは整数に関する命題だけである。多項式に対する類似の命題は別の結果であり、ここでは証明しない。
証明
正の整数線形結合からなる集合を
\[S=\{ax+by:x,y\in\mathbb Z,\ ax+by>0\}\]とおく。
| この集合は空でない。$a,b$ は同時に 0 ではないので、少なくとも一方は 0 でない。$a\ne0$ の場合、$a>0$ なら $x=1$、$a<0$ なら $x=-1$ とし、$y=0$ とおけば $ax+by= | a | >0$ となる。$a=0$ の場合は $b\ne0$ である。このとき $x=0$ とし、$y$ の符号を $b$ と同じに選べば $ax+by= | b | >0$ となる。 |
整列原理により、$S$ には最小の元 $m$ が存在する。したがって、ある $x_0,y_0\in\mathbb Z$ に対して $m=ax_0+by_0$ であり、$m>0$ である。
正の整数 $m$ で $a$ を割り、余りをとると、ある $q,r\in\mathbb Z$ に対して
\[a=qm+r,\qquad 0\le r<m\]となる。$m=ax_0+by_0$ だから、
\[r=a-qm=a(1-qx_0)+b(-qy_0)\]であり、$r$ も $a,b$ の整数線形結合である。もし $r>0$ なら $r\in S$ かつ $r<m$ となり、$m$ の最小性に反する。ゆえに $r=0$ であり、$m\mid a$ である。同じ議論を $b$ に適用すれば $m\mid b$ も得られる。
逆に、$c$ が $a,b$ の任意の公約数ならば、すべての整数線形結合、特に $m=ax_0+by_0$ を割り切る。したがって、$a,b$ のすべての公約数は $m$ を割り切る。$m\mid a$ および $m\mid b$ と合わせると、$m$ は正の最大公約数である。つまり $m=g$ であり、すでに得た表示から $ax_0+by_0=g$ となる。
最後に、すべての線形結合を特定する。$g$ は $a,b$ の両方を割り切るので、任意の $x,y\in\mathbb Z$ に対して $g\mid ax+by$ である。したがって、すべての線形結合は $g$ の倍数である。一方、任意の $n\in\mathbb Z$ について、$ax_0+by_0=g$ に $n$ を掛けると
\[ng=a(nx_0)+b(ny_0)\]を得る。これは $a,b$ の整数線形結合である。ゆえに、線形結合全体はちょうど $g$ の倍数全体であり、証明が完了する。