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

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

- 作者：David（道雾轩）
- 专栏：符号计算的艺术（https://daiw.org/manual/symbolic-computing.md）
- 最后更新：2026-10-01
- 原文：https://daiw.org/manual/symbolic-computing/factor-gcd
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

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

有了[多项式除法](https://daiw.org/manual/symbolic-computing/polynomials)，我们能问最有用的一类问题：一个多项式能拆成哪些「零件」的乘积？两个多项式有没有「公共零件」？这就是**因式分解**和**最大公因式（GCD）**——符号代数的两把利器。

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

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

```python
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)$ 明明能拆啊？

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

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

<Callout type="info">
  **同一个多项式，在不同的[系数域](https://daiw.org/manual/symbolic-computing/polynomials)上，因式分解的答案不同。** $x^2-2$ 在**有理数**域（$\mathbb{Q}$）上不可约（拆出来会用到 $\sqrt2$，而 $\sqrt2$ 不是有理数）；但**扩张**这个域、把 $\sqrt2$ 请进来，它立刻就能分解：

  ```python
  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)$」。域，决定了代数的边界。
</Callout>

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

两个多项式的**最大公因式（GCD）**，是能同时整除它们的「最大」多项式。求法和整数 GCD 一模一样——**辗转相除**，只不过把整数取余换成[多项式取余](https://daiw.org/manual/symbolic-computing/polynomials)：

```python
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` 就干这个：

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

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

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

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

<Callout type="warn">
  **反直觉：分解多项式（在有理数域上）其实是「容易」的——存在多项式时间算法，而分解大整数至今没有。** 这两件事听着像，难度却天差地别：
  - **整数分解**：把 $2048$ 位的大数分解成质因数，是**公认的难题**（否则 RSA 就破了）。
  - **多项式分解**：把一个有理数系数多项式分解，有**高效算法**（Berlekamp、Zassenhaus，以及理论上多项式时间的 LLL / van Hoeij 方法）——CAS 能轻松分解几百次的多项式。

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

## 小结与下一章

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

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

## 参考文献

- [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