辗转相除法与 Bézout 等式

条件

设 $f(x),g(x)\in K[x]$ 不全为零。

结论

1. 存在性：$f,g$ 的最大公因式 $\gcd (f,g)$（ALG-DEF-003）存在，且可由辗转相除法（Euclid 算法）经有限步求出。
2. Bézout 等式：存在 $u(x),v(x)\in K[x]$ 使 $$u(x)f(x)+v(x)g(x)=\gcd (f,g).$$
3. 互素判据：$f,g$ 互素 $⟺$ 存在 $u,v\in K[x]$ 使 $uf+vg=1$。

几何/直觉理解

辗转相除法把”求公因式”化为反复用带余除法降次：余数的次数严格递减，像不断折叠的尺子，有限步后必然落到零，最后一个非零余式就是最大公因式。

核心恒等式：由带余除法 $f=qg+r$（ALG-THM-001），任何同时整除 $g,r$ 的多项式也整除 $f$，反之亦然，故

$$\gcd (f,g)=\gcd (g,r).$$

这把一对多项式替换成”次数更低的一对”，正是算法每一步在做的事。

Bézout 等式的直觉是：$\gcd (f,g)$ 不只是”最大的公因式”，它还能被 $f,g$ 线性组合（系数取多项式）表出——这比整除性强得多，是后续唯一分解、互素消去等论证的总开关。

证明

第 1 步（算法与存在性）。 不妨 $g\ne 0$。反复施行带余除法（ALG-THM-001）：

$$\begin{array}{rlr}f& =q_{1}g+r_1,& 0\le \mathrm{deg}{r}_1<\mathrm{deg}g,\\ g& =q_2{r}_1+r_2,& 0\le \mathrm{deg}{r}_2<\mathrm{deg}{r}_1,\\ r_1& =q_3{r}_2+r_3,& \cdots \\ & ⋮& \\ r_{k-1}& =q_{k+1}{r}_k+r_{k+1},& \mathrm{deg}{r}_{k+1}<\mathrm{deg}{r}_k,\\ r_k& =q_{k+2}{r}_{k+1}+0.& \end{array}$$

余式次数 $\mathrm{deg}{r}_1>\mathrm{deg}{r}_2>\cdots \ge 0$ 严格递减，故有限步后必有余式为 $0$。设最后一个非零余式为 $r_{k+1}$。

由核心恒等式 $\gcd (f,g)=\gcd (g,r_1)=\gcd (r_1,r_2)=\cdots =\gcd (r_k,r_{k+1})=\gcd (r_{k+1},0)$。而 $r_{k+1}\mid r_k$（末行余 $0$），故 $\gcd (r_{k+1},0)$ 即 $r_{k+1}$ 的首一化。于是 $r_{k+1}$（首一化后）就是 $\gcd (f,g)$，存在性得证。

第 2 步（Bézout 等式）。 自最后一个非零余式逐级回代：

$$r_{k+1}=r_{k-1}-q_{k+1}{r}_k,$$

再把 $r_k=r_{k-2}-q_k{r}_{k-1}$ 代入，依次上推，每一步都把 $r_{k+1}$ 表为前两个余式的多项式组合，最终表为 $f,g$ 的组合：

$$r_{k+1}=u_{0}f+v_{0}g,u_0,v_0\in K[x].$$

首一化（乘以常数）得 $uf+vg=\gcd (f,g)$。$■$

第 3 步（互素判据）。

• （$\Rightarrow$）若 $\gcd (f,g)=1$，由第 2 步直接得 $uf+vg=1$。
• （$\Leftarrow$）若 $uf+vg=1$，则 $f,g$ 的任一公因式 $c$ 整除左端 $uf+vg=1$，故 $\mathrm{deg}c=0$，即公因式只有非零常数，$\gcd (f,g)=1$。$■$

常见错误

• ✗ 误以为 Bézout 系数 $u,v$ 唯一。它们不唯一：$(u+tg,v-tf)$ 对任意 $t\in K[x]$ 也成立。通常加上 $\mathrm{deg}u<\mathrm{deg}g$、$\mathrm{deg}v<\mathrm{deg}f$ 的约束才唯一。
• ✗ 把”$f,g$ 无公共根”当作”互素”。在非代数闭域上二者不等价—— 反例：$x^2+1$ 与 $x^2+2$ 在 $\mathbb{R}[x]$ 互素（$uf+vg=1$ 可解），但用”找根”无从判断。可靠判据是辗转相除是否终于非零常数。
• ✗ 把算法用于系数环不是域的 $\mathbb{Z}[x]$。带余除法要求首项系数可逆（ALG-THM-001），$\mathbb{Z}[x]$ 上算法可能卡住；此时 $\gcd$ 需借助高斯引理而非朴素辗转相除。
• ✗ 忘记首一化导致”$\gcd$ 不唯一”的错觉。最大公因式本就相差非零常数，规定首一才唯一。

推论与应用

• 互素版 Euclid 引理：$\gcd (f,g)=1$ 且 $f\mid gh\Rightarrow f\mid h$（两端乘 $h$ 于 $uf+vg=1$）。
• 不可约的素性：不可约 $p$ 满足 $p\mid gh\Rightarrow p\mid g$ 或 $p\mid h$——这是 ALG-THM-002 唯一分解唯一性的核心引理。
• 一次同余 / 中国剩余定理的多项式版求解。

链接

• 前置：ALG-DEF-003 最大公因式与互素、ALG-THM-001 带余除法
• 关键应用：ALG-THM-002 唯一分解定理（Bézout ⇒ 不可约的素性 ⇒ 分解唯一）
• 推广：欧氏环（Euclidean Domain）上 Bézout 等式的一般理论

跨专业应用

• 密码学：整数版扩展欧几里得算法求模逆元 $a^{-1}\mathrm{mod}n$，是 RSA 私钥生成、椭圆曲线点运算的核心；多项式版用于 ${\mathbb{F}}_q[x]$ 上的求逆
• 编码理论：BCH / Reed–Solomon 码译码中，用扩展欧几里得解”关键方程”求错误定位多项式与错误值多项式（Sugiyama 算法）
• 符号计算：CAS 求有理函数部分分式分解、求多项式互素性均以辗转相除为底层