ベズーの等式

$S=\{ax+by : x,y\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$ とおく。これは空でない($|a|$ または $|b|$ を含む)ので、整列原理により最小元 $d=ax_0+by_0$ を持つ。$a$ を $d$ で割った余りを考え、$d$ の最小性を用いると余りは $0$ でなければならないことが分かり、$d\mid a$。同様に $d\mid b$。$a,b$ の任意の公約数は $ax_0+by_0=d$ を割り切るので、$d=\gcd(a,b)$ である。