贝祖等式

设 $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)$。