一次不定方程

它说明最大公约数不仅是“最大的公共因子”,而且确实可以表示为 $a$ 与 $b$ 的整数组合——这正是使 $ax+by=c$ 可解性判据成立的关键事实。

考虑集合 $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$ 时的裴蜀等式。

它彻底解决了问题:一次整除检验就能判定可解性,一旦得到任意一个解,一个关于 $t$ 的单参数族就给出所有其余的解——无需猜测。

($\Rightarrow$)若 $(x,y)$ 是整数解,则 $d=\gcd(a,b)$ 同时整除 $ax$ 和 $by$,故整除 $ax+by=c$。因此 $d \mid c$ 是必要条件。

($\Leftarrow$)设 $d \mid c$,记 $c=de$。由裴蜀等式存在 $u_0,v_0$ 使 $au_0+bv_0=d$。两边乘以 $e$ 得 $a(u_0e)+b(v_0e)=de=c$,故 $(x_0,y_0)=(u_0e,\,v_0e)$ 是一个整数解。这证明了可解性。

现固定一个解 $(x_0,y_0)$,设 $(x,y)$ 为任意另一个解。用 $ax+by=c$ 减去 $ax_0+by_0=c$ 得 $a(x-x_0)+b(y-y_0)=0$,即 $a(x-x_0)=-b(y-y_0)$。两边除以 $d$:$\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)$,由于 $\gcd(a/d,\,b/d)=1$,因子 $\frac{b}{d}$ 必整除 $x-x_0$(互素的标准推论:若 $p\mid mn$ 且 $\gcd(p,m)=1$ 则 $p\mid n$)。故 $x-x_0=\frac{b}{d}t$,其中 $t$ 为某整数,代回得 $y-y_0=-\frac{a}{d}t$。

反之,对任意整数 $t$,将 $x=x_0+\frac{b}{d}t,\ y=y_0-\frac{a}{d}t$ 代入 $ax+by$ 得 $ax_0+by_0+t\left(\frac{ab}{d}-\frac{ab}{d}\right)=c+0=c$,验证了每一对这样的数确实都是解。因此解集恰好是 $x=x_0+\dfrac{b}{d}t,\ \ y=y_0-\dfrac{a}{d}t\ \ (t\in\mathbb{Z})$。