附录2 - 求最大公约式

两个多项式 $f(x)$，$g(x)$ 的最大公约式 $\gcd(f(x), g(x))$ 的严格定义是：

1. 是公约式
2. 能被任何公约式整除（即最大）

要求 $f(x)$ 和 $g(x)$ 的最大公约式，不妨设
$r_{-1} = f(x)$, $r_0 = g(x)$。
连续使用带余除法：
$r_{-1} = q_1 r_0 + r_1 \quad (\deg(r_1) < \deg(r_0))$
$r_0 = q_2 r_1 + r_2 \quad (\deg(r_2) < \deg(r_1))$
$\vdots$
$r_{k-2} = q_k r_{k-1} + r_k \quad (\deg(r_k) < \deg(r_{k-1}))$
$r_{k-1} = q_{k+1} r_k + 0$

因为余式的次数不断严格递减，且次数是非负整数，该过程必定在有限步内终止（余式为 $0$）。最后一个非零余式 $r_k(x)$ 即为最大公约式（通常最后乘以一个常数使其首项系数为 1，但本质是同一个多项式）。

我们需要证明两点：
(1) $r_k$ 是 $f$ 和 $g$ 的公约式；
(2) $f$ 和 $g$ 的任何公约式都能整除 $r_k$。

证明 $r_k$ 是公约式（自下而上）：
从倒数第一个等式 $r_{k-1} = q_{k+1} r_k$ 可以看出， $r_k \mid r_{k-1}$。代入倒数第二个等式
$r_{k-2} = q_k r_{k-1} + r_k$，因为 $r_k \mid r_{k-1}$ 且 $r_k \mid r_k$，所以 $r_k \mid r_{k-2}$。
以此类推，逐步向上倒推，最终可以得到
$r_k \mid r_0$（即 $g(x)$）以及 $r_k \mid r_{-1}$（即 $f(x)$）。
所以 $r_k(x)$ 是公约式。

证明任何公约式都整除 $r_k$（自上而下）：
设 $d(x)$ 是 $f(x)$ 和 $g(x)$ 的任意一个公约式，即 $d \mid r_{-1}$ 且 $d \mid r_0$。
由第一个等式 $r_1 = r_{-1} - q_1 r_0$，因为 $d$ 整除右边的两项，所以
$d \mid r_1$。
由第二个等式 $r_2 = r_0 - q_2 r_1$，因为 $d \mid r_0$ 且 $d \mid r_1$，所以
$d \mid r_2$。
以此类推，逐步向下推导，最终必然得到
$d \mid r_k$。
结论： $r_k(x)$ 满足最大公约式的定义。