高等代数 · 第 P72 集 · 七：公因式、最大公因式、辗转相除法

☰本集目录

◎学习目标

理解公因式的概念：能同时整除两个多项式的多项式；理解最大公因式的定义及其两个条件（是公因式 + 任何公因式都能整除它）；
掌握辗转相除法：通过反复做带余除法，逐步降低余式次数，最终求得两个多项式的最大公因式；
理解并掌握Bézout 等式：\(K[x]\) 中任意两个多项式 \(f(x), g(x)\) 的最大公因式可以表示为它们的线性组合 \(u(x)f(x) + v(x)g(x)\)；
理解最大公因式的唯一性：任意两个最大公因式相伴（差一个非零常数倍）；
掌握首一最大公因式的记号 \(\big(f(x),\, g(x)\big)\)，并理解其不随数域的扩大而改变的重要性质（为 P73 铺垫）。

1公因式与最大公因式的定义 ⏱ 00:02

设 \(K\) 是一个数域，\(f(x), g(x) \in K[x]\)。如果存在 \(d(x) \in K[x]\) 满足：

\(d(x) \mid f(x)\)，且
\(d(x) \mid g(x)\)，

则称 \(d(x)\) 为 \(f(x)\) 与 \(g(x)\) 的一个公因式（common divisor）。显然，任何非零常数多项式（零次多项式）都是 \(f(x)\) 与 \(g(x)\) 的公因式。⏱ 00:51

我们希望寻找一个最大的公因式。自然地，人们会想到"次数最高"的公因式，但这样定义有两个问题：01:10

抽象地给出两个多项式时，难以直接"判决"哪个公因式次数最高；
这种方法不能涵盖所有情况（例如其中一个多项式为零多项式时）。

定义 · 最大公因式设 \(f(x), g(x) \in K[x]\)。如果 \(d(x) \in K[x]\) 满足以下两个条件，则称 \(d(x)\) 为 \(f(x)\) 与 \(g(x)\) 的一个最大公因式（greatest common divisor，简称 GCD）：

\text{(1) } d(x) \mid f(x) \text{ 且 } d(x) \mid g(x) \quad (\text{是公因式}); \] \[ \text{(2) 对任意 } c(x) \in K[x]，\text{若 } c(x) \mid f(x) \text{ 且 } c(x) \mid g(x)，\text{则 } c(x) \mid d(x).

条件 (2) 的含义是：任何公因式都能整除 \(d(x)\)。当 \(d(x) \neq 0\) 时，这意味着任何公因式的次数都不超过 \(d(x)\) 的次数；但当 \(d(x) = 0\) 时（仅当 \(f = g = 0\) 时出现），条件仍然成立且更加简洁。

几个简单例子

\(\big(f(x),\, 0\big) = f(x)\)：因为 \(f(x) \mid f(x)\) 且 \(f(x) \mid 0\)，且任何 \(f(x)\) 的公因式显然整除 \(f(x)\)。⏱ 04:22
\(\big(0,\, 0\big) = 0\)：零多项式只有零多项式这一个公因式，而 \(0 \mid 0\) 成立，故最大公因式为 \(0\)。⏱ 06:52

2最大公因式的存在性与辗转相除法 ⏱ 08:40

下面考虑 \(f(x), g(x)\) 均不为零多项式的情形，证明最大公因式一定存在，并给出具体求法。

引理 · 带余除法的推论设 \(f(x), g(x) \in K[x]\)，\(g(x) \neq 0\)。若存在等式

f(x) = h(x) \cdot g(x) + r(x),

则 \(f(x)\) 与 \(g(x)\) 的公因式集合，与 \(g(x)\) 与 \(r(x)\) 的公因式集合完全相同。因此

\big(f(x),\, g(x)\big) = \big(g(x),\, r(x)\big).

引理证明

正向：设 \(c(x) \mid f(x)\) 且 \(c(x) \mid g(x)\)。由 \(r(x) = f(x) - h(x)g(x)\)，根据命题 3（若 \(c\mid a\) 且 \(c\mid b\)，则 \(c\mid (a-hb)\)），得 \(c(x) \mid r(x)\)。所以 \(c(x)\) 也是 \(g(x)\) 与 \(r(x)\) 的公因式。⏱ 11:51

反向：设 \(c(x) \mid g(x)\) 且 \(c(x) \mid r(x)\)。由 \(f(x) = h(x)g(x) + r(x)\)，得 \(c(x) \mid f(x)\)。所以 \(c(x)\) 也是 \(f(x)\) 与 \(g(x)\) 的公因式。⏱ 12:34

两集合相同，故最大公因式相等。

辗转相除法（欧几里得算法）设 \(f(x), g(x) \in K[x]\)，\(g(x) \neq 0\)。反复应用带余除法：

\begin{aligned} f(x) &= h_1(x) \cdot g(x) + r_1(x), & \deg r_1 < \deg g, \\ g(x) &= h_2(x) \cdot r_1(x) + r_2(x), & \deg r_2 < \deg r_1, \\ r_1(x) &= h_3(x) \cdot r_2(x) + r_3(x), & \deg r_3 < \deg r_2, \\ &\;\;\vdots \\ r_{k-2}(x) &= h_k(x) \cdot r_{k-1}(x) + r_k(x), & \deg r_k < \deg r_{k-1}, \\ r_{k-1}(x) &= h_{k+1}(x) \cdot r_k(x) + 0. \end{aligned}

由于余式的次数严格递减： \[ \deg g > \deg r_1 > \deg r_2 > \cdots > \deg r_k \geq 0, \] 这是一个严格递减的自然数序列，不可能无限进行下去，因此必定在有限步内得到零余式。⏱ 19:27

最后一步的非零余式 \(r_k(x)\)（即除以 0 时的除式）就是 \(f(x)\) 与 \(g(x)\) 的一个最大公因式。

关键结论反复使用引理可得：

\big(f,\, g\big) = \big(g,\, r_1\big) = \big(r_1,\, r_2\big) = \cdots = \big(r_{k-1},\, r_k\big) = r_k.

最后一个非零余式 \(r_k(x)\) 即为所求的最大公因式。⏱ 23:32

3Bézout 等式 ⏱ 24:30

在辗转相除的过程中，把每个余式向上回代，可以得到一个重要结论：

定理（Bézout 等式）设 \(f(x), g(x) \in K[x]\)，不全为零。则它们的最大公因式 \(d(x) = \big(f(x),\, g(x)\big)\) 可以表示为 \(f(x)\) 与 \(g(x)\) 的线性组合，即存在 \(u(x), v(x) \in K[x]\) 使得

d(x) = u(x) \cdot f(x) + v(x) \cdot g(x).

证明（逆向回代法）

从辗转相除的最后一个非零余式 \(r_k(x)\) 出发，它的表达式是： \[ r_k(x) = r_{k-2}(x) - h_k(x) \cdot r_{k-1}(x). \] 而上一步有 \(r_{k-1}(x) = r_{k-3}(x) - h_{k-1}(x) \cdot r_{k-2}(x)\)，代入后可将 \(r_{k-1}\) 表为 \(r_{k-2}\) 与 \(r_{k-3}\) 的线性组合。⏱ 24:30

逐层向上回代，最终可将 \(r_k(x) = d(x)\) 表为 \(f(x)\) 与 \(g(x)\) 的线性组合 \(u(x)f(x) + v(x)g(x)\)。

当 \(g(x) = 0\) 时，\(d(x) = f(x) = 1 \cdot f(x) + 0 \cdot g(x)\)，等式同样成立。⏱ 01:46

意义这是 \(K[x]\) 中关于加法和乘法的第二个重要等式（第一个是带余除法）。它与带余除法一起，构成了整个多项式理论的核心工具。⏱ 02:05

4最大公因式的唯一性 ⏱ 02:24

定理 · 唯一性（相伴性）设 \(d(x)\) 与 \(d'(x)\) 都是 \(f(x)\) 与 \(g(x)\) 的最大公因式，则 \(d(x)\) 与 \(d'(x)\) 相伴（即 \(d(x) \mid d'(x)\) 且 \(d'(x) \mid d(x)\)，等价于存在非零常数 \(c \in K^*\) 使得 \(d'(x) = c \cdot d(x)\)）。

证明

因为 \(d(x)\) 是最大公因式，且 \(d'(x)\) 也是公因式，由定义条件 (2) 得 \(d'(x) \mid d(x)\)。⏱ 03:26

同理，\(d(x) \mid d'(x)\)。因此 \(d(x)\) 与 \(d'(x)\) 互相整除，即相伴。⏱ 03:50

这意味着最大公因式在相伴的意义下是唯一确定的——任意两个最大公因式只差一个非零常数倍。⏱ 04:01

5首一最大公因式 ⏱ 04:56

当 \(f(x), g(x)\) 不全为零时，它们的最大公因式是非零多项式，可以将其⏱ 05:05首项系数提出后归一化，得到一个首一（leading coefficient = 1）的最大公因式。

记号规定用 \(\big(f(x),\, g(x)\big)\) 表示 \(f(x)\) 与 \(g(x)\) 的首一最大公因式。

特别地，首一最大公因式不随数域的扩大而改变：⏱ 07:47

定理 · 首一最大公因式不变性设 \(E \supseteq K\) 为数域的扩域，\(f(x), g(x) \in K[x]\)。则

\big(f(x),\, g(x)\big)_{K[x]} = \big(f(x),\, g(x)\big)_{E[x]}.

证明思路：在 \(K[x]\) 中对 \(f, g\) 做辗转相除法，每一步的商和余式仍在 \(K[x]\) 中（因为做带余除法只涉及系数的加减乘除，不超出 \(K\)）。因此得到的最后一个非零余式 \(r_k(x) \in K[x]\) 就是 \(K[x]\) 中的 GCD。同时，这个计算过程也完全可以在 \(E[x]\) 中进行，且过程完全相同，故 \(r_k(x)\) 也是 \(E[x]\) 中的 GCD。⏱ 07:47 再化为首一形式后，两者相等。

重要推论这个性质说明：判断两个多项式是否互素（即 \(\big(f,g\big) = 1\)），只需要在原始数域 \(K\) 中计算即可，无需考虑扩域。这一结论将在 P73 用于证明互素性也不随数域扩大而改变。⏱ 08:55

★重点回顾

1

最大公因式的定义：\(d\mid f\) 且 \(d\mid g\)，且对任意公因式 \(c\) 有 \(c\mid d\)。这个"整除"定义比"次数最高"更优越，兼容了零多项式情形。

2

辗转相除法：通过反复带余除法，将 \(\big(f,g\big)\) 转化为 \(\big(g,r_1\big)\)，再转化为 \(\big(r_1,r_2\big)\)，……，直到余式为 0，最后的非零余式即为 GCD。

3

Bézout 等式：\(\big(f,g\big) = u(x)f(x) + v(x)g(x)\)。证明方法是把辗转相除的最后一步余式逐层向上回代。

4

唯一性：任意两个最大公因式相伴（差一个非零常数倍）。

5

首一最大公因式记号 \(\big(f,g\big)\)；且它不随数域扩大而改变——这是后续证明互素性不变性的基础。

⚠易错点提醒

常见错误

最大公因式不唯一：任意两个 GCD 相伴，而非相等。只有首一最大公因式才是唯一确定的。
\(\big(f,0\big) = f\)，而非 \(0\)：只有当 \(f=g=0\) 时，\(\big(f,g\big)=0\)。
辗转相除过程中余式次数严格递减：这是算法必定终止的保证，不能假设余式次数可以不变或增加。
不要混淆"公因式"和"最大公因式"：任何公因式都能整除最大公因式（定义条件 2），反之不成立。
Bézout 等式中 \(u(x), v(x)\) 不唯一：不同的辗转相除路径会得到不同的 \(u, v\)，但只要满足等式即可。

✎自测与作业

用辗转相除法求 \(\big(x^3 - 3x + 2,\; x^2 - 1\big)\)，并将结果表示为两个多项式的线性组合。
证明：若 \(\big(f,g\big) = 1\) 且 \(f \mid gh\)，则 \(f \mid h\)。（此性质将在 P73 中作为互素性质 1 出现。）
设 \(\big(f,g\big) = d\)，证明对任意非零常数 \(c \in K\)，有 \(\big(cf, g\big) = d\)（取首一形式后相等）。
验证首一最大公因式不随数域扩大而改变：取 \(f(x) = x^2 - 2, g(x) = x^2 - 3x + 2\)，分别在 \(\mathbb{Q}[x]\) 和 \(\mathbb{R}[x]\) 中计算 \(\big(f,g\big)\)，比较结果。
（思考题）若 \(f(x) = x^4 + 4x^3 + 6x^2 + 4x + 1\)，\(g(x) = x^3 + 2x^2 + 2x + 1\)，求 \(\big(f,g\big)\) 并用 Bézout 等式表出。

下一集预告第 P73 集 · 八：互素性、互素性不随数域扩大而改变，互素的定义与 Bézout 刻画，以及三条互素性质（尤其是性质 1：若 \((f,g)=1\) 且 \(f\mid hg\)，则 \(f\mid h\)）。