附录5 - 高斯引理

『本原多项式』：一个整系数多项式 $f(x) \in \mathbb{Z}[x]$ 称为本原多项式（Primitive Polynomial），如果它的所有系数的最大公约数为 $1$。

『高斯引理』：两个本原多项式的乘积依然是本原多项式。

证明：
利用素数的整除性质反证，设：
$f(x) = a_0 + a_1x + \dots + a_nx^n$ 和
$g(x) = b_0 + b_1x + \dots + b_mx^m$
是两个本原多项式。设它们的乘积为

$h(x) = f(x)g(x) = c_0 + c_1x + \dots + c_{n+m}x^{n+m}$

其中 $h(x)$ 的第 $k$ 项系数为：

$c_k = \sum_{i+j=k} a_i b_j = a_0b_k + a_1b_{k-1} + \dots + a_kb_0$

假设 $h(x)$ 不是本原多项式。那么 $h(x)$ 的所有系数存在一个大于 $1$ 的公约数，因此必然存在一个素数 $p$，使得 $p$ 整除 $h(x)$ 的每一个系数 $c_k$。
因为 $f(x)$ 是本原的，$p$ 不可能整除 $f(x)$ 的所有系数。设 $a_r$ 是 $f(x)$ 中第一个不被 $p$ 整除的系数（即对于所有 $i < r$，$p \mid a_i$）。
同理，因为 $g(x)$ 也是本原的，设 $b_s$ 是 $g(x)$ 中第一个不被 $p$ 整除的系数（即对于所有 $j < s$，$p \mid b_j$）。
现在我们考察 $h(x)$ 中的第 $r+s$ 项系数 $c_{r+s}$：

$c_{r+s} = a_0b_{r+s} + \dots + a_{r-1}b_{s+1} + a_rb_s + a_{r+1}b_{s-1} + \dots + a_{r+s}b_0$

我们分析这个和式中的各项：
对于排在 $a_rb_s$ 前面的项 $a_ib_j$ ($i < r$)，由于 $p \mid a_i$，所以 $p \mid a_ib_j$。
对于排在 $a_rb_s$ 后面的项 $a_ib_j$ ($j < s$)，由于 $p \mid b_j$，所以 $p \mid a_ib_j$。
根据假设，$p$ 整除所有的 $c_k$，因此 $p \mid c_{r+s}$。将 $a_rb_s$ 单独留在等式一边：

$a_rb_s = c_{r+s} - \sum_{i<r} a_ib_{r+s-i} - \sum_{j<s} a_{r+s-j}b_j$

等号右边的每一项都能被 $p$ 整除，因此等号左边的 $a_rb_s$ 也必须能被 $p$ 整除，即 $p \mid a_rb_s$。
因为 $p$ 是素数，根据素数的性质，必然有 $p \mid a_r$ 或 $p \mid b_s$。
但这与我们之前设定的“$a_r$ 和 $b_s$ 是不被 $p$ 整除的”这一前提直接矛盾！
结论：假设不成立，$h(x)$ 必然是本原多项式。引理得证。

『高斯引理的推论（一般情况）』：设 $f(x) \in \mathbb{Z}[x]$ 是一个整系数多项式。若 $f(x)$ 在有理数域 $\mathbb{Q}$ 上可以分解为两个多项式 $G(x), H(x) \in \mathbb{Q}[x]$ 的乘积，即 $f(x) = G(x)H(x)$。
那么，必定存在有理数 $r, s$，使得 $g(x) = r G(x)$ 和 $h(x) = s H(x)$ 都是整系数多项式，且 $f(x) = g(x)h(x)$。
(简而言之：有理数域上的因式分解，一定能转化为整数环上的因式分解。)

在证明之前，我们需要明确一个简单的代数事实：
任何一个非零的有理系数多项式 $P(x) \in \mathbb{Q}[x]$，都可以唯一地（差一个正负号）表示为：
$P(x) = \frac{a}{b} P^*(x)$
其中， $a, b$ 是互素的整数， $P^*(x) \in \mathbb{Z}[x]$ 是一个本原多项式（即所有系数的最大公约数为 $1$）。

提取方法很简单：先提出所有分数系数分母的最小公倍数 $\frac{1}{b}$，使其变成整系数；再提出此时所有系数的最大公约数 $a$，剩下的自然就是本原多项式了。再把 $\frac{a}{b}$ 约分为最简形式即可。

已知 $f(x) = G(x)H(x)$，其中 $f(x) \in \mathbb{Z}[x]$， $G(x), H(x) \in \mathbb{Q}[x]$。
第1步：将 $G(x)$ 和 $H(x)$ 本原化。
根据上述小引理，我们可以将 $G(x)$ 和 $H(x)$ 写成：

$G(x) = \frac{a_1}{b_1} G^*(x)$

$H(x) = \frac{a_2}{b_2} H^*(x)$

其中 $a_1, b_1$ 互素， $a_2, b_2$ 互素；且 $G^*(x), H^*(x)$ 都是整系数的本原多项式。代入原式：

$f(x) = \frac{a_1 a_2}{b_1 b_2} G^*(x)H^*(x)$

令 $a = a_1 a_2$， $b = b_1 b_2$，交叉相乘得到：
$b \cdot f(x) = a \cdot G^*(x)H^*(x)$

第2步：利用高斯引理进行约束。
根据我们之前证明的高斯引理，$G^*(x)$ 和 $H^*(x)$ 是本原多项式，那么它们的乘积 $G^*(x)H^*(x)$ 依然是本原多项式。
我们考察等式 $b \cdot f(x) = a \cdot [G^*(x)H^*(x)]$ 两边多项式的系数的最大公约数（我们称之为多项式的容度，Content）。
左边： $f(x)$ 是整系数多项式，设其系数的最大公约数为 $d$。那么左边系数的最大公约数是 $b \cdot d$。
右边： 因为 $G^*(x)H^*(x)$ 是本原多项式（系数最大公约数为 $1$），所以右边系数的最大公约数就是 $a$。
由于等式两边的多项式完全相等，它们系数的最大公约数也必须相等（不考虑正负号），因此有：
$b \cdot d = \pm a \implies \frac{a}{b} = \pm d$

第3步：得出结论。
这说明，常数因子 $\frac{a}{b}$ 实际上是一个整数 $\pm d$！代回最初的等式：

$f(x) = \frac{a}{b} G^*(x)H^*(x) = (\pm d) \cdot G^*(x)H^*(x)$

因为 $d$ 是整数，且 $G^*(x), H^*(x)$ 是整系数多项式，我们可以分配这个整数 $d$。例如，令：
$g(x) = (\pm d) \cdot G^*(x) \in \mathbb{Z}[x]$
$h(x) = H^*(x) \in \mathbb{Z}[x]$
这样 $f(x) = g(x)h(x)$，且 $g, h$ 都是整系数多项式。
回顾定义， $g(x)$ 是 $G(x)$ 的有理数倍， $h(x)$ 是 $H(x)$ 的有理数倍。
一般情况的推论得证。

『高斯引理的推论（首一多项式特例）』：设 $f(x) \in \mathbb{Z}[x]$ 是一个首一整系数多项式。若 $f(x)$ 可以分解为两个首一的有理系数多项式 $G(x), H(x) \in \mathbb{Q}[x]$ 的乘积。
那么，$G(x)$ 和 $H(x)$ 必然本身就是整系数多项式（即 $G(x), H(x) \in \mathbb{Z}[x]$）

证明过程：
步骤 1. 根据我们在“第三部分”证明的结论：
既然 $f(x)$ 可以在有理数域上分解，那么它必定可以分解为两个整系数多项式的乘积，且这两个整系数多项式分别是 $G(x)$ 和 $H(x)$ 的有理数倍。
即存在 $g(x), h(x) \in \mathbb{Z}[x]$，使得：
$f(x) = g(x)h(x)$
且存在有理数 $c_1, c_2$，使得
$g(x) = c_1 G(x)$， $h(x) = c_2 H(x)$。

步骤 2. 分析最高次项系数：因为 $g(x)$ 和 $h(x)$ 都是整系数多项式，设 $g(x)$ 的最高次项系数为整数 $l_g$， $h(x)$ 的最高次项系数为整数 $l_h$。
在等式 $f(x) = g(x)h(x)$ 中，两边多项式的最高次项系数必须相等。因为 $f(x)$ 是首一多项式（最高次项系数为 $1$），所以：
$l_g \cdot l_h = 1$
在整数环 $\mathbb{Z}$ 中，两个整数的乘积为 $1$ 只有两种可能：
$l_g = 1 \text{ 且 } l_h = 1$ ，或者
$l_g = -1 \text{ 且 } l_h = -1$

步骤 3. 还原回有理多项式：

由于题目已知 $G(x)$ 和 $H(x)$ 都是首一多项式（最高次项系数为 $1$），
代入 $g(x) = c_1 G(x)$ 可以得出：

$g(x) \text{ 的最高次项系数 } l_g = c_1 \cdot 1 = c_1$ ，同理代入 $h(x) = c_2 H(x)$得出：
$h(x) \text{ 的最高次项系数 } l_h = c_2 \cdot 1 = c_2$

由步骤 2 可知， $c_1$ 和 $c_2$ 只能是 $1$ 或 $-1$。也就是说， $c_1$ 和 $c_2$ 实际上是整数 $\pm 1$。

步骤 4. 得出结论：既然 $c_1 = \pm 1$，那么 $G(x) = \frac{1}{c_1} g(x) = \pm g(x)$。因为 $g(x)$ 是整系数多项式，所以 $G(x)$ 必然也是整系数多项式。同理可证 $H(x)$ 也是整系数多项式。

结论：定理得证。