附录3 - 裴蜀定理

『多项式的裴蜀定理』：若 $d(x) = \gcd(f(x), g(x))$，则存在多项式 $u(x), v(x) \in F[x]$，使得 $u(x)f(x) + v(x)g(x) = d(x)$。

证明（利用非空集合的最小次数原理）：
构造一个集合 $S$，包含 $f(x)$ 和 $g(x)$ 的所有非零线性组合：

$S = \{ a(x)f(x) + b(x)g(x) \mid a(x), b(x) \in F[x], \text{且该组合不为 } 0 \}$

因为 $F[x]$ 中的多项式次数都是非负整数，根据良序原理（非空非负整数集合必有最小值），集合 $S$ 中必定存在一个次数最低的多项式，设为 $m(x)$。即存在 $u(x), v(x)$ 使得
$m(x) = u(x)f(x) + v(x)g(x)$
我们要证明 $m(x)$ 就是最大公约式 $d(x)$。
首先，用 $f(x)$ 除以 $m(x)$，得到

$f(x) = q(x)m(x) + r(x)$，其中 $r(x) = 0$ 或 $\deg(r) < \deg(m)$。

将 $m(x)$ 的表达式代入：

$r(x) = f(x) - q(x)[u(x)f(x) + v(x)g(x)] = [1 - q(x)u(x)]f(x) - [q(x)v(x)]g(x)$

这说明 $r(x)$ 也可以表示为 $f(x)$ 和 $g(x)$ 的线性组合。
如果 $r(x) \neq 0$，那么 $r(x) \in S$。但 $\deg(r) < \deg(m)$，这与 $m(x)$ 是 $S$ 中次数最低的多项式矛盾！
因此，$r(x)$ 必须为 $0$，即 $m(x) \mid f(x)$。
同理可证 $m(x) \mid g(x)$。
因此 $m(x)$ 是 $f(x)$ 和 $g(x)$ 的公约式。

另一方面，设 $d_1(x)$ 是 $f(x)$ 和 $g(x)$ 的任一公约式，则
$d_1(x) \mid f(x)$ 且
$d_1(x) \mid g(x)$
因此 $d_1(x)$ 必然整除它们的线性组合 $u(x)f(x) + v(x)g(x)$，即
$d_1(x) \mid m(x)$。
这证明了 $m(x)$ 就是最大公约式 $d(x)$。
结论：定理得证。

『整数的裴蜀定理』：对任意两个不全为零的整数 $a, b$，存在整数 $x, y$，使得 $ax + by = \gcd(a, b)$。

证明（逻辑与多项式情况完全同构）：
构造集合 $S$，包含 $a$ 和 $b$ 的所有正线性组合：
$S = \{ au + bv > 0 \mid u, v \in \mathbb{Z} \}$
因为 $a, b$ 不全为零，集合 $S$ 必然非空（例如若 $a \neq 0$，则 $a \cdot a + b \cdot 0 = a^2 > 0 \in S$）。
根据自然数集的良序原理，集合 $S$ 中存在一个最小的正整数，设为 $d$。
即存在整数 $x, y$ 使得 $d = ax + by$。我们证明 $d = \gcd(a, b)$。
用 $a$ 除以 $d$，根据整数带余除法：$a = qd + r$，其中 $0 \le r < d$。
代入 $d = ax + by$：
$r = a - qd = a - q(ax + by) = a(1 - qx) + b(-qy)$
这说明 $r$ 也是 $a$ 和 $b$ 的线性组合。
如果 $r > 0$，则 $r \in S$。但 $r < d$，这与 $d$ 是 $S$ 中的最小正整数矛盾！
因此 $r = 0$，即 $d \mid a$。同理可证 $d \mid b$。
所以 $d$ 是 $a$ 和 $b$ 的公约数。

若 $c$ 是 $a$ 和 $b$ 的任意公约数，即 $c \mid a$ 且 $c \mid b$
则 $c$ 必然整除 $ax + by$，即 $c \mid d$。

结论：因此 $d$ 就是最大公约数，定理得证。

以多项式为例，设

$r_{-1}=f(x),\quad r_0=g(x)$

并记录

$r_{-1}=1\cdot f+0\cdot g,\quad r_0=0\cdot f+1\cdot g$

如果某一步带余除法为

$r_{i-2}=q_i r_{i-1}+r_i$

那么

$r_i=r_{i-2}-q_i r_{i-1}$

也就是说，只要把 $r_{i-2}$ 和 $r_{i-1}$ 已经记录好的线性表示代入，就能得到 $r_i$ 的线性表示。一直做到余式为 $0$，最后一个非零余式就是最大公约式；它对应的那组线性表示，就是要找的裴蜀表达式。

整数情形完全相同，只是把多项式带余除法换成整数带余除法。

例如，多项式情形中若

$f(x)=x^3+2x^2+2x-3,\quad g(x)=x^2+3x+4$

辗转相除过程是：

$f(x)=(x-1)g(x)+(x+1)$

$g(x)=(x+2)(x+1)+2$

$x+1=\frac{x+1}{2}\cdot 2+0$

所以最后一个非零余式是 $2$，最大公约式取首一形式就是 $1$。现在倒回去代入：

$2=g(x)-(x+2)(x+1)$

又因为

$x+1=f(x)-(x-1)g(x)$

所以

$2=g(x)-(x+2)[f(x)-(x-1)g(x)]$

$=-(x+2)f(x)+[1+(x+2)(x-1)]g(x)$

$=-(x+2)f(x)+(x^2+x-1)g(x)$

两边同除以 $2$，得到

$1=-\frac{x+2}{2}f(x)+\frac{x^2+x-1}{2}g(x)$

再看一个整数例子：

$252=1\cdot198+54$

$198=3\cdot54+36$

$54=1\cdot36+18$

最后一个非零余数是 $18$。倒回去代入：

$18=54-36$

$=54-(198-3\cdot54)$

$=4\cdot54-198$

$=4(252-198)-198$

$=4\cdot252-5\cdot198$

所以这里的裴蜀系数可以取 $x=4,\ y=-5$。