高等代数 · 第 P71 集 · 四十：公因式、最大公因式、辗转相除法

☰本集目录

◎学习目标

理解公因式的概念：若 \(d(x)\mid f(x)\) 且 \(d(x)\mid g(x)\)，则 \(d(x)\) 称为 \(f(x)\) 与 \(g(x)\) 的一个公因式；
掌握最大公因式（GCD）的定义：\(d(x)\) 是 \(f(x),g(x)\) 的公因式，且任何公因式都能整除 \(d(x)\)；
理解 GCD 的存在性（利用带余除法和辗转相除法构造）与唯一性（相伴意义下唯一）；
掌握辗转相除法（Euclidean Algorithm）求多项式最大公因式的具体步骤；
理解互素概念 \((f,g)=1\) 及其贝祖等式：存在 \(u(x),v(x)\in K[x]\) 使得 \(u(x)f(x)+v(x)g(x)=(f(x),g(x))\)。

1公因式的概念 ⏱ 00:01

回顾上一集（P70）的整除关系：在多项式环 \(K[x]\) 中，若多项式 \(d(x)\) 能整除 \(f(x)\)，且 \(d(x)\) 也能整除 \(g(x)\)，即

d(x)\mid f(x) \quad \text{且} \quad d(x)\mid g(x),

则称 \(d(x)\) 为 \(f(x)\) 与 \(g(x)\) 的一个公因式。⏱ 00:30

备注零次多项式（非零常数）一定整除任意多项式，因此任何两个多项式至少有一个公因式——零次多项式就是它们的一个公因式。

自然地，我们希望找到一个"最大的"公因式。一个直观的想法是取次数最高的公因式，但这样会遇到两个问题：⏱ 01:40

给定两个多项式，要列出所有公因式再比较次数，既不现实也不好操作；
这种方法无法统一处理包含零多项式的情况。

因此丘老师引入了基于整除关系的最大公因式定义，它既统一了理论框架，又天然包含了零多项式的特殊情形。⏱ 02:16

2最大公因式的定义 ⏱ 02:20

定义 · 最大公因式设 \(f(x),g(x)\in K[x]\)。若 \(d(x)\in K[x]\) 满足以下两个条件：

\(d(x)\) 是 \(f(x)\) 与 \(g(x)\) 的公因式，即 \(d(x)\mid f(x)\) 且 \(d(x)\mid g(x)\)；
对 \(f(x)\) 与 \(g(x)\) 的任意公因式 \(c(x)\)，都有 \(c(x)\mid d(x)\)；

则称 \(d(x)\) 为 \(f(x)\) 与 \(g(x)\) 的一个最大公因式（Greatest Common Divisor，GCD），记作

d(x) = (f(x),\,g(x)).

为什么要用"整除"而不是"次数最大"来定义？关键在于它自然包含了零多项式的情形：⏱ 03:19

特例 1：\((f(x),0)\) 对任意 \(f(x)\)，由于 \(f(x)\mid f(x)\) 且 \(f(x)\mid 0\)，故 \(f(x)\) 是 \(f(x)\) 与 \(0\) 的公因式。又对任意公因式 \(c(x)\)（必有 \(c(x)\mid f(x)\)），条件 2 自动满足。因此

(f(x),\,0) = f(x).

特例 2：\((0,0)\) 任何多项式 \(c(x)\) 都整除 \(0\)，故任何多项式都是 \(0\) 与 \(0\) 的公因式。由定义，最大公因式应被所有公因式整除——唯一满足此条件的是 \(0\) 本身：

(0,\,0) = 0.

注意这里最大公因式是次数最低的（零多项式，次数为 \(-\infty\)），而非次数最高的，体现了该定义的精妙之处。⏱ 04:45

3最大公因式的存在性与唯一性 ⏱ 08:40

当 \(f(x),g(x)\) 均非零时，它们的最大公因式是否存在？是否唯一？本节逐一回答这两个问题。⏱ 09:15

3.1 关键引理

引理设 \(f(x),g(x)\in K[x]\)，\(g(x)\neq 0\)，且有带余除法等式

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

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

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

证明

（\(\Rightarrow\)）设 \(c(x)\mid f(x)\) 且 \(c(x)\mid g(x)\)。由 \(r(x)=f(x)-h(x)g(x)\) 可知 \(c(x)\mid r(x)\)。故 \(c(x)\) 也是 \(g(x)\) 与 \(r(x)\) 的公因式。⏱ 11:23

（\(\Leftarrow\)）设 \(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

由此，两个多项式组的公因式完全一致，进而最大公因式也相同。证毕。

3.2 存在性证明（辗转相除法）

对 \(f(x),g(x)\)（均非零）反复做带余除法：⏱ 16:30

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

由于余式的次数构成严格递减的自然数序列：\(\deg g > \deg r_1 > \deg r_2 > \cdots\)，该过程必在有限步后终止（余式为 \(0\)）。⏱ 19:00

定理 · 存在性与唯一性对任意 \(f(x),g(x)\in K[x]\)（不全为零），\((f(x),g(x))\)存在，且在相伴意义下唯一（即任意两个最大公因式相差一个非零常数倍）。⏱ 23:30

唯一性证明

设 \(d_1(x)\) 和 \(d_2(x)\) 都是 \(f(x),g(x)\) 的最大公因式。由定义：

\(d_1\mid f,\; d_1\mid g\)，且对任意公因式 \(c\) 有 \(c\mid d_1\)；
\(d_2\mid f,\; d_2\mid g\)，且对任意公因式 \(c\) 有 \(c\mid d_2\)。

因 \(d_2\) 是公因式，故 \(d_2\mid d_1\)；同理 \(d_1\mid d_2\)。因此 \(d_1\) 与 \(d_2\) 相伴，即存在非零常数 \(c\in K\) 使 \(d_1(x)=c\cdot d_2(x)\)。证毕。

在实际计算中，我们通常取首一最大公因式（最高次项系数为 1）作为标准代表。⏱ 25:00

4辗转相除法求最大公因式 ⏱ 16:00

由引理 \((f,g)=(g,r_1)=(r_1,r_2)=\cdots=(r_{k-1},r_k)\)，最后一步余式为 \(0\)，而 \((r_k,0)=r_k\)，故 ⏱ 21:30

辗转相除法对 \(f(x),g(x)\)（\(\deg f\geq\deg g\)）反复执行带余除法，直到余式为 \(0\)，最后一个非零余式 \(r_k(x)\) 即为 \(f(x)\) 与 \(g(x)\) 的一个最大公因式。

为什么一定终止？

每次带余除法后，余式的次数严格下降：\(\deg r_{i+1} < \deg r_i\)。这些次数都是非负整数（或 \(-\infty\) 表示零多项式）。

自然数序列不可能无限严格递减（良序原理），因此必在有限步后出现余式 \(r_k=0\)，过程终止。⏱ 19:27

计算示例求 \((x^3-1,\; x^2-1)\)（在有理数域 \(\mathbb{Q}[x]\) 中）：

\begin{aligned} x^3-1 &= x\cdot(x^2-1) + (x-1),\\ x^2-1 &= (x+1)\cdot(x-1) + 0. \end{aligned}

最后一个非零余式是 \(x-1\)，故 \((x^3-1,\; x^2-1)=x-1\)（已为首一）。

5互素与贝祖（Bézout）等式 ⏱ 24:30

定义 · 互素若 \((f(x),g(x))=1\)（即最大公因式为常数多项式 \(1\)），则称 \(f(x)\) 与 \(g(x)\)互素（coprime）。

5.1 贝祖等式

定理 · 贝祖等式（Bézout's Identity）设 \(f(x),g(x)\in K[x]\)，则存在 \(u(x),v(x)\in K[x]\) 使得

u(x)\,f(x) + v(x)\,g(x) = (f(x),\,g(x)).

特别地，若 \((f,g)=1\)，则存在 \(u,v\in K[x]\) 使 \(u(x)f(x)+v(x)g(x)=1\)。⏱ 25:50

证明（反向代入法）

在辗转相除法的每一步等式中，把余式表成前两项的线性组合：

\begin{aligned} r_1 &= f - h_1 g,\\ r_2 &= g - h_2 r_1 = g - h_2(f-h_1 g) = -h_2 f + (1+h_2 h_1)g,\\ r_3 &= r_1 - h_3 r_2 = \cdots \end{aligned}

从倒数第二步开始，逐步向上代入，最终可将最后一个非零余式 \(r_k=(f,g)\) 表为 \(f\) 与 \(g\) 的线性组合 \(u(x)f(x)+v(x)g(x)\)。证毕。

丘老师在课堂上指出：这个结论是从辗转相除法的倒数第二个等式反向代入得到的。⏱ 24:40

5.2 互素的充分必要条件

推论 \(f(x)\) 与 \(g(x)\) 互素 \(\iff\) 存在 \(u(x),v(x)\in K[x]\) 使 \(u(x)f(x)+v(x)g(x)=1\)。

证明

（\(\Rightarrow\)）若 \((f,g)=1\)，由贝祖等式直接得证。

（\(\Leftarrow\)）若 \(uf+vg=1\)，设 \(d=(f,g)\)，则 \(d\mid f\) 且 \(d\mid g\)，故 \(d\mid(uf+vg)=1\)，即 \(\deg d=0\)，从而 \((f,g)=1\)（首一化）。证毕。

★重点回顾

1

公因式：\(d\mid f\) 且 \(d\mid g\iff d\) 是 \(f,g\) 的公因式。任何两个多项式至少有一个公因式（零次多项式）。

2

最大公因式定义：\(d=(f,g)\iff d\mid f,\;d\mid g\)，且对任意公因式 \(c\) 有 \(c\mid d\)。用整除而非次数来定义，统一处理了含零多项式的情形。

3

特殊情形：\((f,0)=f\)，\((0,0)=0\)。注意 \((0,0)\) 的最大公因式是次数最低的（零多项式），而非次数最高的。

4

辗转相除法：\((f,g)=(g,r_1)=(r_1,r_2)=\cdots=(r_{k-1},r_k)=r_k\)（\(r_k\) 为最后一个非零余式）。终止性由次数严格递减的自然数序列不可能无限下降保证。

5

贝祖等式：\((f,g)=uf+vg\)。最大公因式可表为两多项式的线性组合，这是通过反向代入辗转相除法的每一步得到的。

6

互素：\((f,g)=1\)。等价于存在 \(u,v\) 使 \(uf+vg=1\)（互素的充要条件）。

7

唯一性：GCD 在相伴意义下唯一（相差非零常数倍）。实际中取首一 GCD 作为标准代表。

⚠常见误区提醒

常见错误

误用"次数最高"定义 GCD：对两个多项式而言，所有公因式中次数最高的那个并不好计算，而且无法统一处理含零多项式的情形（如 \((0,0)\) 的任何多项式都是公因式，没有"次数最高"的）。
混淆 \((f,0)\) 与 \((0,0)\)：\((f,0)=f\)（对任意 \(f\)），而 \((0,0)=0\)。两者不同，不要混为一谈。
认为 GCD 唯一：GCD 在相伴意义下唯一，即若有 \(d_1,d_2\) 都是 \(f,g\) 的 GCD，则 \(d_1=c\cdot d_2\)（\(c\neq 0\) 为常数）。若要唯一，需取首一最大公因式。
辗转相除法终止条件记错：终止于余式为 \(0\) 的那一步，最后一个非零余式才是 GCD，不是最后一步的除式。
误认为互素就是没有公因式：互素是指最大公因式为常数（即只有零次多项式作为公因式），并非"没有公因式"——零次多项式始终是公因式。
贝祖等式中的 \(u,v\) 不唯一：满足 \(uf+vg=(f,g)\) 的多项式 \(u,v\) 有无穷多组，只需找到一组即可。

✎自测题

求 \((x^3-3x+2,\; x^2-1)\) 的最大公因式（在 \(\mathbb{Q}[x]\) 中），并验证你的结果。
证明：若 \((f,g)=1\) 且 \(f\mid gh\)，则 \(f\mid h\)。（提示：用贝祖等式。）
求 \((x^4+2x^3+x^2+x+1,\; x^3+x+1)\) 的最大公因式。
设 \((f,g)=d\)，证明：\((f/d,\; g/d)=1\)。
（思考）为什么 \((0,0)=0\)？从定义出发说明：零多项式是自身与自身的最大公因式。
（选做）用辗转相除法求 \((2x^3-3x^2+3x-2,\; x^3-x^2-x+1)\)，并将其表为这两个多项式的线性组合（验证贝祖等式）。

下一集预告第 P72 集 · 八：互素性的进一步讨论——互素性不随数域的扩大而改变，即若 \(K\subseteq L\)，则 \(f,g\in K[x]\) 在 \(K[x]\) 中互素当且仅当它们在 \(L[x]\) 中也互素。