裴蜀等式

考虑集合 $S=\{au+bv : u,v\in\mathbb{Z}\}\cap\mathbb{Z}_{>0}$,即 $a$ 与 $b$ 的所有严格正整数组合。由于 $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$ 时的裴蜀等式。