多项式带余除法

条件

设 $f(x),g(x)\in K[x]$，且 $g(x)\ne 0$。

结论

存在唯一一对多项式 $q(x),r(x)\in K[x]$ 使

$$f(x)=g(x)\cdot q(x)+r(x),\text{其中 }r(x)=0\text{ 或 }\mathrm{deg}r<\mathrm{deg}g.$$

称 $q(x)$ 为商，$r(x)$ 为余式。

几何/直觉理解

多项式带余除法是整数带余除法的”次数镜像”：

• 整数：$a=bq+r,0\le r<|b|$（用绝对值衡量”小”）
• 多项式：$f=gq+r,\mathrm{deg}r<\mathrm{deg}g$（用次数衡量”小”）

每次”除”的过程是”减掉 $g$ 的最高次倍式以降低 $f$ 的次数”， 直到次数低于 $g$ 为止——这就是手工长除法的精确表述。

唯一性来自次数的良序性：每一步降次都是确定的。

证明

存在性（构造）：对 $\mathrm{deg}f$ 用强归纳。

• 若 $\mathrm{deg}f<\mathrm{deg}g$：取 $q=0,r=f$ 即可。
• 若 $\mathrm{deg}f=n\ge m=\mathrm{deg}g$：设 $f$ 的首项系数为 $a_n$，$g$ 的首项系数为 $b_m$。 令 $f_1(x)=f(x)-\frac{a_n}{b_m}{x}^{n-m}g(x)$。 关键观察：$f_1$ 的 $x^n$ 项被消去，故 $\mathrm{deg}{f}_1<n$。 由归纳假设，存在 $q_1,r$ 使 $f_1=g{q}_1+r$，且 $r=0$ 或 $\mathrm{deg}r<m$。 代回： $$f=\frac{a_n}{b_m}{x}^{n-m}g+g{q}_1+r=g\left(\frac{a_n}{b_m}{x}^{n-m}+q_1\right)+r.$$ 取 $q=\frac{a_n}{b_m}{x}^{n-m}+q_1$ 即得。

唯一性：设 $f=g{q}_1+r_1=g{q}_2+r_2$，两式相减：

$$g(q_1-q_2)=r_2-r_1.$$

若 $q_1\ne q_2$，则左侧 $\mathrm{deg}g(q_1-q_2)\ge \mathrm{deg}g=m$； 但右侧 $\mathrm{deg}(r_2-r_1)<m$（两者次数都 $<m$），矛盾。 故 $q_1=q_2$，从而 $r_1=r_2$。$■$

常见错误

• ✗ 漏检条件 $g\ne 0$。零多项式无次数，定理不适用——除以 0 在多项式环里同样无意义。
• ✗ 忽视余式的次数约束 $\mathrm{deg}r<\mathrm{deg}g$，写成”任何分解 $f=gq+r$ 都对”。 反例：$x^2+1=x\cdot x+1$（合法，$\mathrm{deg}1=0<\mathrm{deg}x=1$）， 但 $x^2+1=(x+1)(x-1)+2$ 中 $r=2$ 也合法——两种写法对应不同的 $g$。 唯一性说的是”对给定 $g$，$(q,r)$ 唯一”，不是”$f$ 只有一种分解”。
• ✗ 把”$K[x]$ 上的带余除法”误用到”$\mathbb{Z}[x]$ 上”。 $K$ 必须是域（每个非零系数可逆），否则首项系数 $b_m$ 不一定可除。 反例：在 $\mathbb{Z}[x]$ 中 $f=x,g=2x$，求商需要 $1/2\notin \mathbb{Z}$。

推论与应用

• 余数定理：$f(c)=$ $f(x)$ 除以 $(x-c)$ 的余数。
• 因式定理：$(x-c)\mid f(x)⟺f(c)=0$。
• 用于辗转相除法（Euclid 算法）求最大公因式。
• 用于 ALG-THM-002 唯一分解定理证明。

链接

• 前置：ALG-DEF-001、ALG-DEF-002
• 用于定理：ALG-THM-002
• 推广：欧氏环（Euclidean Domain）的一般理论

跨专业应用

• 符号计算：Mathematica / SymPy 等系统的核心化简算法 PolynomialReduce、PolynomialQuotient、PolynomialRemainder 均以本定理为底层
• 编码理论：CRC（循环冗余校验）算法本质是 ${\mathbb{F}}_2[x]$ 中的多项式带余除法——发送端发送 $f\cdot x^k-r$，接收端用 $g$ 整除验错
• 密码学：椭圆曲线运算、AES 密钥扩展中均需有限域上多项式除法