因式分解与最大公因式 · 系数域的魔法 · 符号计算的艺术

把 x⁴-1 拆成（x-1）(x+1)（x²+1），把 x²-2 拆成含 √2 的因子——因式分解的答案取决于「系数从哪个数集来」。这一章讲清因式分解、多项式版欧几里得算法求 GCD，以及一个反直觉的事实：多项式因式分解其实是「快」的，不像整数分解那样难。

因式分解与最大公因式 · 系数域的魔法

有了多项式除法，我们能问最有用的一类问题：一个多项式能拆成哪些「零件」的乘积？两个多项式有没有「公共零件」？这就是因式分解和最大公因式（GCD）——符号代数的两把利器。

因式分解：拆成不可约的积

factor 把多项式拆成不可约因子（拆不动了的最小零件）的乘积：

from sympy import *
x = symbols('x')

print(factor(x**4 - 1))          # (x - 1)*(x + 1)*(x**2 + 1)
print(factor(x**2 - 2))          # x**2 - 2      —— 拆不动?

$x^4-1$ 干净地拆成三个因子。但 $x^2-2$ 却原样返回——SymPy 说它「不可约」。可 $x^2-2=(x-\sqrt2)(x+\sqrt2)$ 明明能拆啊？

关键：因式分解取决于「系数域」

这里藏着计算机代数一个核心观念：「能不能分解」不是绝对的，而是相对于「系数允许从哪个数集来」。

同一个多项式，在不同的系数域上，因式分解的答案不同。 $x^2-2$ 在有理数域（ $\mathbb{Q}$ ）上不可约（拆出来会用到 $\sqrt2$ ，而 $\sqrt2$ 不是有理数）；但扩张这个域、把 $\sqrt2$ 请进来，它立刻就能分解：

print(factor(x**2 - 2))                    # x**2 - 2         (在 ℚ 上)
print(factor(x**2 - 2, extension=sqrt(2))) # (x - sqrt(2))*(x + sqrt(2))

默认 factor 在有理数域上工作（这是最常用、最「安全」的选择）。你可以用 extension= 把根式请进来，或用 factor(..., gaussian=True) 请进虚数单位 $i$ 。「在哪个域上分解」由你指定——这不是模糊，而是精确：CAS 一丝不苟地区分「 $x^2+1$ 在实数域不可分」和「在复数域可分成 $(x-i)(x+i)$ 」。域，决定了代数的边界。

最大公因式：多项式版的辗转相除

两个多项式的最大公因式（GCD），是能同时整除它们的「最大」多项式。求法和整数 GCD 一模一样——辗转相除，只不过把整数取余换成多项式取余：

print(gcd(x**2 - 1, x**2 - 3*x + 2))    # x - 1

$x^2-1=(x-1)(x+1)$ ， $x^2-3x+2=(x-1)(x-2)$ ，公共因子是 $x-1$ 。SymPy 不需要先因式分解——它直接用欧几里得算法反复做多项式除法取余，几步就得到 GCD，又快又稳。

GCD 最日常的用途是约分：化简一个分式时，把分子分母的公因子消掉，靠的正是 GCD。SymPy 的 cancel 就干这个：

print(cancel((x**2 - 1) / (x - 1)))     # x + 1   —— 约掉公因子 (x-1)

(x²-1)/(x-1) 的分子分母有公因子 $x-1$ ，约掉得 $x+1$ 。你在化简有理函数、通分、判断两个分式是否相等时，背后都是 GCD 在默默干活。

一个反直觉的事实：分解多项式，其实很「快」

说到「因式分解」，很多人会立刻联想到整数分解——RSA 加密的安全性，正建立在「把一个大整数分解成质因数极其困难」上。那多项式因式分解是不是也很难？

反直觉：分解多项式（在有理数域上）其实是「容易」的——存在多项式时间算法，而分解大整数至今没有。 这两件事听着像，难度却天差地别：

整数分解：把 $2048$ 位的大数分解成质因数，是公认的难题（否则 RSA 就破了）。
多项式分解：把一个有理数系数多项式分解，有高效算法（Berlekamp、Zassenhaus，以及理论上多项式时间的 LLL / van Hoeij 方法）——CAS 能轻松分解几百次的多项式。

为什么差这么多？直觉上，多项式带着「次数」「系数」等丰富的结构可供算法利用（比如可以先在有限域上分解、再「抬升」回来），而一个光秃秃的大整数几乎没有结构可抓。「分解」这个词一样，难度却由对象的结构决定——这是计算复杂性里一个很有意思的对照。

小结与下一章

因式分解 factor 把多项式拆成不可约因子，但结果取决于系数域： $x^2-2$ 在有理数域不可分、在含 $\sqrt2$ 的扩域可分（用 extension=）。GCD gcd 用多项式版欧几里得算法（辗转相除）求公因式，是约分 cancel 的引擎。有趣的是，多项式分解有高效算法，不像整数分解那样难——难度由结构决定。

单个 / 两个多项式我们会玩了。可现实里常是一整组多元多项式方程要一起解（比如两条曲线的交点）。线性方程组有高斯消元，那非线性的多项式方程组呢？答案是那颗被誉为计算机代数明珠的 Gröbner 基。👉 Gröbner 基：多项式方程组的高斯消元。

参考文献

[1] von zur Gathen & Gerhard.《Modern Computer Algebra》, ch. 14-16 —— 因式分解算法。
[2] Geddes, Czapor & Labahn.《Algorithms for Computer Algebra》—— GCD 与因式分解。
[3] SymPy 文档.「factor, gcd, cancel.」https://docs.sympy.org/latest/modules/polys/reference.html

因式分解与最大公因式 · 系数域的魔法