ベズーの等式

$a$ と $b$ の正の整数結合全体からなる集合 $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ を考える。$a,b$ はどちらも $0$ ではないので $S$ は空でなく($|a|$ または $|b|$ を含む)、整列原理により $S$ には最小元 $d=au_0+bv_0>0$ が存在する。

$d\mid a$ を示す:$a=qd+r$($0\le r<d$)と割る。すると $r=a-qd=a-q(au_0+bv_0)=a(1-qu_0)+b(-qv_0)$ はそれ自体 $a,b$ の整数結合である。もし $r>0$ なら $r$ は $S$ に属し $d$ より小さくなり最小性に矛盾する。よって $r=0$、すなわち $d\mid a$ である。$a$ の代わりに $b$ で同じ議論をすれば $d\mid b$ も分かる。

$d$ は $a$ と $b$ の公約数なので $d\le \gcd(a,b)$ である。逆に、$a$ と $b$ の任意の公約数 $e$ は $au_0+bv_0=d$ を割り切るので $e\le d$。$e=\gcd(a,b)$ とすれば $\gcd(a,b)\le d$ を得る。

両方の不等式を合わせると $d=\gcd(a,b)$ であり、構成より $d=au_0+bv_0$ である。これはまさに $u=u_0,v=v_0$ とするベズーの等式である。