模素数约化的不可约证书

为什么一定要保留次数 ​

反设 $f$ 有正次数的有理系数分解。由Gauss 引理理路多项式内容与 Gauss 引理Polynomial content · Gauss lemma for polynomials · 多项式 Gauss 引理分离多项式的系数公因子，证明本原乘积仍本原，并把分式域中的因式分解还原到原环。，可以写成整数系数分解 $f=gh$，且两因子次数都大于零。首项系数相乘等于 $a_n$；由于 $p\nmid a_n$，两个首项都不会在模 $p$ 后变成零。所以

违反 $\overline{f}$ 的不可约性。这就是全部提升机制：一个原有分解若不能借降次藏起来，就会暴露在较小的系数域中。

首项条件不能省。取

它在 $\mathbb{Q}[x]$ 中可约，但模 $2$ 后变成 $x+1$，这是不可约的一次式。因子 $2x+1$ 被压成常数 $1$，于是原来的二次分解消失了。不可约的是一个降次后的对象，不能给原二次式作证。

四次例子：无根之后还要查二次因子 ​

令

模 $2$ 后它不降次。在 ${\mathbb{F}}_2$ 的两个元素上，$\overline{f}(0)=\overline{f}(1)=1$，所以没有一次因子。但是四次可约还可能是两个二次因子的乘积；只查点值不够。

${\mathbb{F}}_2[x]$ 中唯一的首一不可约二次多项式是 $q=x^2+x+1$。理由是：首一二次若没有根，常数项必须为 $1$；在 $1$ 处不为零又迫使一次项系数为 $1$。其余首一二次都有一次因子。

用 $x^2\equiv x+1(\mathrm{mod}q)$，依次得到 $x^3\equiv 1$、$x^4\equiv x$，所以

因此唯一可能的不可约二次因子也不整除 $\overline{f}$。若四次式可约，至少有一个不可约因子次数不超过 $2$；两类都被排除，所以 $\overline{f}$ 不可约，进而 $f$ 在 $\mathbb{Q}[x]$ 中不可约。证书只有三次检查：在 $0,1$ 处的值，以及除以 $q$ 的余数。

一般地，次数为 $n$ 的域上多项式若可约，至少有一个不可约因子次数不超过 $\lfloor n/2\rfloor$。在有限域中，可以枚举这些首一候选并做除法；这给出有限的验证过程，虽然不是大次数分解的高效算法。更高效的分解方法见Berlekamp 算法理路Berlekamp 多项式因式分解算法Berlekamp factorization algorithm · Berlekamp polynomial factorization计算有限域商代数的 Frobenius 不动子空间，并以 GCD 从中确定性分离不可约因子。。

“没有有理根”究竟排除了什么 ​

若 $f=a_n{x}^n+\cdots +a_0\in \mathbb{Z}[x]$ 有既约有理根 $u/v$，其中 $gcd(u,v)=1$、$v>0$，把 $v^{n}f(u/v)=0$ 分别对 $u$ 和 $v$ 考察整除，得到

例如第二条来自 $v\mid a_n{u}^n$，而 $u^n$ 与 $v$ 互素；第一条同理。首一整数多项式的有理根因此必为整数。这种筛选只排除一次因子。

二次或三次多项式一旦可约，因子次数分拆必包含 $1$，所以“没有底域中的根”恰好等价于不可约。四次开始，$2+2$ 是新的可能。例如

没有有理根：任何根都满足 $x^2=2$ 或 $x^2=3$，有理数平方的素因子指数都是偶数，不可能等于 $2$ 或 $3$。但右边已经给出两个正次数有理因子。这正是“四次无有理根即不可约”的反例。

约化可约，原式仍可能不可约 ​

$x^2+1$ 在 $\mathbb{Q}[x]$ 中不可约，却在模 $2$ 后成为 $(x+1{)}^2$。所以约化失败只意味着这一份证书没有成功，不意味着找到了原式的有理因子。

更强的局限出现在本单元的目标

它在有理域上不可约，证明见极小多项式中的根式例子理路极小多项式Minimal polynomial以给定代数元为根的首一不可约多项式。；但换遍所有素数都不能得到不可约约化。下面是一个可选的完整验证，也解释了为何这里应换用扩张次数证书。

先有三种恒等式：

对奇素数 $p\ne 3$，$2,3,6$ 在 ${\mathbb{F}}_p$ 中至少有一个是平方。如果 $2$ 或 $3$ 已是平方，无需解释；若二者都是非平方，则它们的乘积是平方。后一事实不用群论也能验证：每个非零平方有恰好两个平方根，所以非零平方占全部非零元素的一半。固定一个非平方 $a$，它乘每个非零平方都得到非平方，且这些结果互不相同，因而恰好得到全部非平方。另一个非平方必可写成 $a{b}^2$，两者的乘积就是 $(ab{)}^2$。

若 $3$ 是平方，第一行是平方差；若 $2$ 是平方，第二行是平方差；若 $6$ 是平方，第三行是平方差。它们分别分成两个二次多项式。剩下的素数也明确可约：模 $2$ 为 $(x+1{)}^4$，模 $3$ 为 $(x^2+1{)}^2$。这并不与提升判据矛盾，因为判据从来没有声称反方向成立。

自测：两次失败能否合成证书 ​

设一个首一五次整数多项式模 $2$ 后恰分成不可约的二次与三次因子，模 $3$ 后恰分成不可约的一次与四次因子。这两次都没有不可约约化，仍能证明原式不可约吗？能。若原式有首一整数因子，其次数在第一次检查中只能为 $2$ 或 $3$，在第二次中只能为 $1$ 或 $4$；没有共同可能。首一性使每次约化都保次数，Gauss 引理排除剩余有理分解。这里使用的是完整因子次数，而不只是一个“可约”标签。