14 带余除法

带余除法 #

这讲讲什么：多项式除以多项式，一定能写成「商 × 除数 + 余式」，且余式的次数严格低于除数——而且商与余式唯一。
前置：多项式的加法、乘法与次数；向量空间的基（05 讲）、线性无关（04 讲）、基同长定理（06 讲）会用在证明里。不熟悉多项式记号也不影响，本讲会把用到的都写出来。
一句话：多项式也能做除法，"大小"用次数衡量，除到"次数不够"就停，停下来的那个就是余式。

---

一、为什么需要它 #

先从一个朴素的问题开始。

你手上有一个多项式 $p(z)$，想知道 $z=3$ 是不是它的零点。最直接的做法是代入算一遍。但如果 $p$ 的次数很高，你又想一次性知道"除掉 $z-3$ 之后剩下什么"，代入就不够用了——你想知道的是结构，不是某个点的值。

或者换个问法：给定 $p$ 和 $s$，能不能像整数那样写

$$p = s\cdot q + r$$

把 $p$ 分解成"$s$ 的倍数 + 一点零头"？如果能，并且这点零头比 $s$ 小，那我们就有了一个可以反复使用的工具。

这件事的价值在于三点：

第一，它把"零点"变成"因式"。 若 $p(\lambda)=0$，则 $p$ 一定能被 $z-\lambda$ 整除。这一句话把"求根"（分析问题）和"分解因式"（代数问题）接上了。04 讲之后的很多结论都要靠它：一个 $m$ 次多项式最多有 $m$ 个零点，正是靠"每找到一个零点就剥掉一个一次因式，次数降一"反复归纳得到的。

第二，它保证多项式是"良定义的对象"。 一个多项式可以写成 $1+2z+3z^2$，也可以写成 $3z^2+2z+1$，还能写成 $(1+z)^2+z^2$。凭什么说这些写法背后是"同一个"多项式、系数是唯一确定的？理由正是：若两组系数给出同一个多项式，相减就得到一个"有非零系数却有无穷多个零点"的多项式，而"零点不超过次数个"这条又是由带余除法推出来的。所以带余除法是"多项式的系数唯一"这条常识的地基。

第三，它是算法。 整数除法你会竖式，多项式除法也能竖式；两者形式几乎一样，只是"退位"变成了"降次"。学会之后，任何一个有理系数多项式除以另一个，你都能手算到底，并且能验算。

---

二、定义与最小例子 #

2.1 先把"次数"的约定补齐 #

写定理之前必须先处理一个麻烦：零多项式没有次数。解决办法是人为规定

$$\deg 0 = -\infty$$

并且约定 $-\infty$ 与整数、与自身的运算规则：

$$-\infty < m,\qquad -\infty + m = -\infty,\qquad -\infty + (-\infty) = -\infty$$

（$m$ 为任意整数。）

为什么要这样规定？因为这样许多结论就不用写例外了。比如

$$\deg(pq) = \deg p + \deg q$$

若 $p=0$ 或 $q=0$，左边是 $-\infty$，右边是 $-\infty + \deg q = -\infty$，等式照样成立。若不允许 $-\infty$，你就得每次补一句"当 $p,q$ 都非零时"。这条约定不是偷懒，是把例外吸收进算术里。

2.2 定理 #

$$p = sq + r$$

且

$$\deg r < \deg s$$

这里 $\mathcal{P}(\mathbb{F})$ 表示系数在域 $\mathbb{F}$ 中的全体多项式，$\mathbb{F}$ 可以是 $\mathbb{R}$ 或 $\mathbb{C}$。

三个词要盯住：

• $s\neq 0$：除数不能是零多项式（和整数里"除数不能是 0"同理）。
• $\deg r < \deg s$：这是"余式比除数小"的准确含义。注意不是"$r$ 的系数比 $s$ 小"，也不是"$r<s$"——多项式之间没有天然的大小顺序，能用来比大小的只有次数。
• 存在唯一：两句都要。只证存在，你不知道"余式"指哪一个；只证唯一，可能根本不存在。

2.3 最小的例子：除不尽时余式就是被除式 #

取 $p(z) = z^2+1$，$s(z) = z^3 - z$。此时 $\deg p = 2 < 3 = \deg s$。

按定理，取

$$q = 0,\qquad r = p = z^2+1$$

则 $p = s\cdot 0 + p$ 显然成立，且 $\deg r = 2 < 3 = \deg s$。验证完毕。

这个例子看着平凡，但它说明了两件事：

1. "次数不够"时商就是零——这正是竖式除法"不够除就停"的严格版本。
2. 定理的证明要分两种情形：$\deg p < \deg s$（如上，一步搞定）与 $\deg p \ge \deg s$（需要真功夫）。后一种情形才是本讲的正文。

再补一个小例子，把 $s$ 取成常数：$p(z) = 5z^3 - 2$，$s(z) = 3$（非零常数，次数为 0）。定理要求 $\deg r < 0$，而次数小于 $0$ 的多项式只有零多项式，所以 $r = 0$，$q = \frac{5}{3}z^3 - \frac{2}{3}$。除以非零常数永远整除——这也符合直觉。

2.4 逐条回看定义 #

条件	在防什么	反例（若不写这条）
$s \neq 0$	零不能作除数	若 $s=0$，$\deg s=-\infty$，要求 $\deg r<-\infty$ 不可能
$\deg r < \deg s$	保证余式"更小"	若只要求 $\deg r \le \deg s$，余式不唯一
存在性	除得下去	在整数系数多项式环上就会失败（见第六节）
唯一性	"余式"这个词有意义	否则无法定义 $p \bmod s$

---

三、几个必须自己算一遍的结论 #

这一节请拿纸笔跟着算。看懂和算过是两件事。

3.1 例一：完整竖式除法 #

题目：把 $p(z) = 2z^4 - 3z^3 + z - 5$ 除以 $s(z) = z^2 + z - 1$（在 $\mathbb{Q}$ 上）。

第一步：补零位。 $p$ 缺 $z^2$ 项，先补成

$$p(z) = 2z^4 - 3z^3 + 0z^2 + z - 5$$

补零位不是形式主义。竖式靠"同次项对齐"工作，缺一项就会错位（见第五节误区 1）。

第二步：削掉最高次项。 当前余式 $R_0 = p$，首项 $2z^4$；除数首项 $z^2$。做

$$2z^4 \div z^2 = 2z^2$$

这就是商的第一项。减去 $2z^2 s$：

$$\begin{aligned} R_0 - 2z^2 s &= (2z^4-3z^3+0z^2+z-5) - 2z^2(z^2+z-1)\\ &= (2z^4-3z^3+0z^2+z-5) - (2z^4+2z^3-2z^2)\\ &= -5z^3 + 2z^2 + z - 5 \end{aligned}$$

记 $R_1 = -5z^3+2z^2+z-5$。注意 $2z^4$ 被消掉了，这是设计好的：每一步都精确消掉当前最高次项。

第三步：重复。 首项 $-5z^3$ 除以 $z^2$ 得 $-5z$：

$$\begin{aligned} R_1 - (-5z)s &= (-5z^3+2z^2+z-5) - (-5z^3-5z^2+5z)\\ &= 7z^2 - 4z - 5 \end{aligned}$$

记 $R_2 = 7z^2-4z-5$。次数从 3 降到 2。

第四步：再来一次。 首项 $7z^2$ 除以 $z^2$ 得 $7$：

$$\begin{aligned} R_2 - 7s &= (7z^2-4z-5) - (7z^2+7z-7)\\ &= -11z + 2 \end{aligned}$$

现在 $R_3 = -11z+2$，$\deg R_3 = 1 < 2 = \deg s$。不够除了，停。

结果：

$$q(z) = 2z^2 - 5z + 7,\qquad r(z) = -11z+2$$

验算（这一步绝不能省）：

$$\begin{aligned} s(z)q(z) &= (z^2+z-1)(2z^2-5z+7)\\ &= 2z^4 - 5z^3 + 7z^2 + 2z^3 - 5z^2 + 7z - 2z^2 + 5z - 7\\ &= 2z^4 - 3z^3 + 0z^2 + 12z - 7 \end{aligned}$$

再加 $r$：

$$s q + r = 2z^4-3z^3+12z-7 + (-11z+2) = 2z^4-3z^3+z-5 = p$$

验算通过。同时确认 $\deg r = 1 < 2$。

3.2 例二：把缺项对齐这件事做对 #

题目：把 $p(z) = z^4 - 1$ 除以 $s(z) = z^2 - 2z + 1$。

这个例子的坑在于 $p$ 只有两项：$z^4$ 和 $-1$。中间 $z^3,z^2,z$ 的系数全是 0。写全：

$$p(z) = z^4 + 0z^3 + 0z^2 + 0z - 1$$

第一步：$z^4 \div z^2 = z^2$。

$$p - z^2 s = (z^4-1) - (z^4-2z^3+z^2) = 2z^3 - z^2 - 1$$

第二步：$2z^3 \div z^2 = 2z$。

$$(2z^3-z^2-1) - 2z(z^2-2z+1) = (2z^3-z^2-1)-(2z^3-4z^2+2z) = 3z^2 - 2z - 1$$

第三步：$3z^2 \div z^2 = 3$。

$$(3z^2-2z-1) - 3(z^2-2z+1) = (3z^2-2z-1)-(3z^2-6z+3) = 4z - 4$$

$\deg(4z-4) = 1 < 2$，停。

$$q(z) = z^2+2z+3,\qquad r(z) = 4z-4$$

验算：

$$\begin{aligned} (z^2-2z+1)(z^2+2z+3) &= z^4+2z^3+3z^2-2z^3-4z^2-6z+z^2+2z+3\\ &= z^4 + 0z^3 + 0z^2 - 4z + 3 \end{aligned}$$

加上 $r = 4z-4$：

$$z^4 - 4z + 3 + 4z - 4 = z^4 - 1 = p$$

通过。顺带看一个现象：$s(z)=z^2-2z+1=(z-1)^2$，而这里余式不为零。这说明 $z^4-1$ 不被 $(z-1)^2$ 整除。

但若改除 $z-1$，操作就完全不同了：由余数定理，余数 $=p(1)=0$，所以 $z-1$ 确实整除 $z^4-1$。

$$\text{被 }(z-1)^2\text{ 除：余 }4z-4\neq0;\qquad \text{被 }(z-1)\text{ 除：余 }0$$

同一个 $p$，除数不同，结论就不同。"整除"永远是"被谁整除"的省略说法——这是本讲最容易含糊的一处，务必写全。

3.3 长除法 vs 综合除法：同一件事的两种排版 #

现在把除数取成一次首一式 $z-\lambda$。这时竖式会退化成一种极省事的写法，叫综合除法（synthetic division）。

题目：把 $p(z) = 2z^3 - 3z^2 + 4z - 5$ 除以 $z-2$，即 $\lambda = 2$。

长除法（照 3.1 的流程）：

$$2z^3 \div z = 2z^2;\quad p - 2z^2(z-2) = z^2+4z-5$$

$$z^2 \div z = z;\quad (z^2+4z-5) - z(z-2) = 6z-5$$

$$6z \div z = 6;\quad (6z-5) - 6(z-2) = 7$$

得 $q = 2z^2+z+6$，$r = 7$。

综合除法（只写系数，除数写成"$2$"）：

$$\begin{array}{c|rrrr} 2 & 2 & -3 & 4 & -5\\ & & 4 & 2 & 12\\ \hline & 2 & 1 & 6 & 7 \end{array}$$

读法：把 $p$ 的系数按降次排一行（缺项补 0）；第一个系数 $2$ 直接落下；乘 $2$ 写在下一位，与该位相加得 $1$；$1\times 2=2$ 写下一位，$4+2=6$；$6\times2=12$，$-5+12=7$。最后一行除末位就是商的系数，末位是余数。

$$q(z) = 2z^2+z+6,\qquad r = 7$$

两者结果一致。为什么能这样省？因为除数首项系数是 $1$，每一步的"除法"都只是除以 1，于是整列运算只剩"乘 $\lambda$ 再相加"。

对照表：

	长除法	综合除法
适用除式	任意非零多项式	只能是 $z-\lambda$（首一、一次）
写什么	完整多项式	只写系数
每步做	除首项、乘、减	乘 $\lambda$、加
本质	反复消最高次项	同一算法的"系数跟踪版"
出错点	缺项错位、符号	漏位、$\lambda$ 的符号写反

3.4 余数定理：除以一次式的余数就是函数值 #

把 3.1 的论证用到一次除式上，立刻得到下面这条。它在本讲的定理里是推论，但用起来比定理还勤。

$$p(\lambda) = (\lambda-\lambda)q(\lambda) + r = r$$

又 $\deg r < \deg(z-\lambda) = 1$，故 $r$ 是常数（或零）。证毕。

注意证明里两个条件各管一件事：

• $\deg r<1$ 保证 $r$ 是常数（不是含 $z$ 的东西）；
• 代入 $z=\lambda$ 保证这个常数等于 $p(\lambda)$。

少任何一个都得不出结论。这也解释了为什么除以 $z^2+1$ 时不能这么干：那时余式次数可以是 1，不是常数，"代入求值"这条路走不通（见误区 4）。

例：3.3 里 $p(z)=2z^3-3z^2+4z-5$ 除以 $z-2$ 得 $r=7$。直接算 $p(2) = 16-12+8-5 = 7$，一致。这不是巧合，是定理。

3.5 因式定理：零点 ↔ 一次因式 #

余数定理取 $r=0$ 的特例，就是最常用的那条：

证明是两行：若 $p(\lambda)=0$，由余数定理 $p = (z-\lambda)q + p(\lambda) = (z-\lambda)q$；反之若 $p=(z-\lambda)q$，代入 $z=\lambda$ 得 $p(\lambda)=0$。

用法一：判断整除。 问 $z-3$ 是否整除 $p(z)=z^3-4z^2+z+6$？

算 $p(3) = 27 - 36 + 3 + 6 = 0$。是。于是

$$z^3-4z^2+z+6 = (z-3)q(z)$$

$q$ 用综合除法求（$\lambda=3$）：

$$\begin{array}{c|rrrr} 3 & 1 & -4 & 1 & 6\\ & & 3 & -3 & -6\\ \hline & 1 & -1 & -2 & 0 \end{array}$$

$q(z) = z^2-z-2 = (z-2)(z+1)$。于是

$$p(z) = (z-3)(z-2)(z+1)$$

零点一次全拿到：$3, 2, -1$。注意这里的效率：直接解三次方程很难，但"猜一个根 + 除一次 + 降一次"就把问题压成了二次。这就是带余除法的实际价值——把高次问题降次。

用法二：证明零点个数上界。 若 $p$ 的次数为 $m$，则 $p$ 在 $\mathbb{F}$ 中最多有 $m$ 个零点。证明是对 $m$ 归纳：找到零点 $\lambda$，剥掉 $(z-\lambda)$ 得次数 $m-1$ 的 $q$，由归纳假设 $q$ 至多 $m-1$ 个零点，而 $p$ 的零点恰是 $q$ 的零点加上 $\lambda$，共至多 $m$ 个。

用法三：证明系数唯一。 若 $p$ 有两组系数不同的表示，相减得一个非零多项式 $h$，它在 $\mathbb{F}$ 中处处为零（因为两种表示在每点取值相同），于是 $h$ 有无穷多个零点——与"至多 $\deg h$ 个"矛盾。故系数唯一。

这条链子值得记住：带余除法 → 因式定理 → 零点个数上界 → 系数唯一 → 多项式作为对象是良定义的。

3.6 为什么证明要用线性代数 #

定理本身可以纯靠"竖式"的思路证（反复消最高次项，次数严格下降，必然停），这个证明更直观。但这里给出的是另一种证明，因为它展示了向量空间的语言怎么用。

设 $n=\deg p$，$m=\deg s$，并设 $n\ge m$（$n<m$ 的情形已在 2.3 处理）。

考虑 $\mathcal{P}_n(\mathbb{F})$（次数不超过 $n$ 的全体多项式，它是 $n+1$ 维向量空间）中的向量组

$$1,\ z,\ \dots,\ z^{m-1},\ s,\ zs,\ \dots,\ z^{n-m}s \tag{3.1}$$

先数长度：前一段 $m$ 个，后一段从 $s$ 到 $z^{n-m}s$ 共 $n-m+1$ 个，总计

$$m + (n-m+1) = n+1 = \dim \mathcal{P}_n(\mathbb{F})$$

再验无关：这个向量组里每个多项式次数各不相同（依次是 $0,1,\dots,m-1$ 和 $m,m+1,\dots,n$）。次数互不相同的多项式组一定线性无关——因为看最高次那一项，它在其他所有多项式里都不出现（或出现次数更低），系数非零就消不掉。

于是它是基：长度为 $n+1$、恰等于维数的线性无关组，必是基（05 讲的扩充定理：可扩成基，而长度已经到顶；也可用 06 讲的基同长定理）。

关键一步：$p\in\mathcal{P}_n(\mathbb{F})$，而 (3.1) 是基，故 $p$ 有唯一的坐标表示

$$\begin{aligned} p(z) &= \underbrace{a_0+a_1z+\cdots+a_{m-1}z^{m-1}}_{=\,r(z)} + \underbrace{b_0 s + b_1 zs + \cdots + b_{n-m}z^{n-m}s}_{=\,s\cdot q(z)}\\ &= r(z) + s(z)\,q(z) \end{aligned}$$

其中

$$r(z) = a_0+a_1z+\cdots+a_{m-1}z^{m-1},\qquad q(z) = b_0+b_1z+\cdots+b_{n-m}z^{n-m}$$

• $\deg r < m = \deg s$（或 $r=0$，此时 $\deg r=-\infty$）——存在性得证；
• 而 $a_i, b_j$ 是坐标，坐标唯一，所以 $r,q$ 唯一——唯一性也得证。

3.7 唯一性的另一种证法（用次数） #

上面的唯一性来自坐标唯一。也可以只用次数不等式直接推出，这个论证更短，值得会：

设两组解 $p = sq_1+r_1 = sq_2+r_2$，且 $\deg r_1,\deg r_2<\deg s$。相减：

$$s(q_1-q_2) = r_2-r_1 \tag{3.2}$$

若 $q_1\neq q_2$，则 $\deg(q_1-q_2)\ge 0$，由 $\deg(pq)=\deg p+\deg q$ 得

$$\deg\big(s(q_1-q_2)\big) = \deg s + \deg(q_1-q_2) \ge \deg s$$

而右边 $\deg(r_2-r_1)\le \max(\deg r_1,\deg r_2) < \deg s$（次数不超过两者最大值，而两者都严格小于 $\deg s$）。

一边 $\ge \deg s$，一边 $<\deg s$，矛盾。故 $q_1=q_2$，代回 (3.2) 得 $r_2-r_1=0$，即 $r_1=r_2$。

---

四、几何直观 / 记忆钩子 #

4.1 次数就是"高度" #

把多项式想成一根按次排的柱子：$z^0$ 位、$z^1$ 位、$z^2$ 位……每位的"高度"是系数。次数就是最高那根柱子的位置。

长除法做的事，说一句话：拿除数的最高柱去削被除式的最高柱，削平一根降一格，直到被除式的最高柱低于除数。

于是"算法一定停"有了直观解释：每次最高柱至少降一格，而降不到负数以下（次数 $\ge 0$ 或 $=-\infty$），所以最多

$$\deg p - \deg s + 1$$

步就停。这就是 3.1 里只走了 3 步的原因（$4-2+1=3$）。

4.2 和十进制除法逐条对照 #

你小学学的竖式除法，本质上就是同一个算法，只是"大小"的度量换成了"位数"：

	整数 $p\div s$	多项式 $p\div s$
写法	$p = sq+r$	$p = sq+r$
比大小的尺子	$0\le r<s$（绝对值）	$\deg r<\deg s$
每步干什么	试商，乘，减	除首项，乘，减
每步效果	被除数有效位数下降	余式次数下降
何时停	余数小于除数	余式次数低于除数
是否唯一	是	是

把"位数"换成"次数"，小学竖式就是多项式竖式。 这条类比几乎能带你走完本讲所有计算。

4.3 三个口诀 #

1. 「补零、对齐、削最高」——竖式三件事，按顺序做。
2. 「除到不够除为止」——"不够除"就是 $\deg r<\deg s$。
3. 「一次式看值，二次式看余」——除式是 $z-\lambda$ 时余数就是 $p(\lambda)$（余数定理）；除式次数 $\ge 2$ 时余式含 $z$，不能直接代值。

4.4 一张图记住"为什么它重要" #

不用画图，记住这条依赖链就行：

$$\text{带余除法}\ \Rightarrow\ \text{余数定理}\ \Rightarrow\ \text{因式定理}\ \Rightarrow\ \begin{cases}\text{零点个数}\le m\\ \text{系数唯一}\\ \text{代数基本定理的分解版}\end{cases}$$

链上每一环都靠上一环，而最底下那一环只用到一件小事：次数可以严格下降。

---

五、常见误区 #

---

六、拓展（可跳过） #

6.1 一路除下去：欧几里得算法与最大公因式 #

有了带余除法，就可以像整数那样"辗转相除"：

$$p = s q_1 + r_1,\quad s = r_1 q_2 + r_2,\quad r_1 = r_2 q_3 + r_3,\ \dots$$

每次余式次数严格下降，必在有限步后得到 $r_{k+1}=0$，此时 $r_k$ 就是 $p$ 与 $s$ 的最大公因式（在相差一个非零常数倍的意义下唯一，若要求首一则完全唯一）。

这条算法在工程上叫欧几里得算法，在代数上说明 $\mathbb{F}[z]$ 是"欧几里得整环"——一个能做带余除法的整环。$\mathbb{Z}$ 与 $\mathbb{F}[z]$ 是这类结构最经典的两个例子。

6.2 代数基本定理：为什么要靠它才能"分到底" #

代数基本定理说：每个非常数的复系数多项式在 $\mathbb{C}$ 中都有零点。注意它只保证至少一个零点。

要得到"$p$ 可分解为一次因式之积"这个更强的结论，得反复做一件事：找到一个零点 $\lambda$，用因式定理剥掉 $(z-\lambda)$，次数降 1，再对新多项式用一次代数基本定理，直到降到常数。每一次"剥"都是一次带余除法（除式为 $z-\lambda$ 的特例）。

所以分工是这样的：

• 代数基本定理负责"存在零点"，它的证明必须用分析学（连续性、极值、甚至刘维尔定理）；
• 带余除法负责"剥因式"，它是纯代数的，只用次数。

两者合起来才有"$m$ 次复系数多项式恰有 $m$ 个零点（计重数）"以及 $\mathbb{C}$ 上的完全分解。少了带余除法，代数基本定理只能停在"有零点"，无法累积成完整分解。

6.3 工程用途：CRC 校验就是一次多项式除法 #

通信与存储里几乎无处不在的 CRC（循环冗余校验），核心就是 $\mathbb{F}_2$ 上的带余除法。

$\mathbb{F}_2 = \{0,1\}$ 只有两个元素，加法是异或（$1+1=0$），减法与加法相同。把一串比特看成一个 $\mathbb{F}_2$ 上多项式的系数，比如 $1011 \leftrightarrow z^3+z+1$。

发端做的事是：

1. 取一个固定的生成多项式 $G(z)$（例如 CRC-32 用的那个 33 项多项式），次数记 $k$；
2. 把消息多项式 $M(z)$ 左移 $k$ 位（即乘 $z^k$），除以 $G(z)$，取余式 $R(z)$；
3. 发送 $z^kM(z)+R(z)$。

收端只要验证"收到的多项式能否被 $G(z)$ 整除"（余式是否为零）。

因为 $\mathbb{F}_2$ 上加减都是异或，竖式除法退化成"移位 + 异或"，没有借位、没有进位，硬件用一串异或门加移位寄存器（LFSR）几拍就算完。这就是 CRC 便宜、快、还查得准的原因。

它能查出什么错，也有确定答案：所有单位错、所有长度 $\le k$ 的突发错、以及（当 $G$ 含因子 $z+1$ 时）所有奇数个比特错。

6.4 一个术语上的提醒 #

$\mathbb{F}[z]$ 里带余除法的"尺子"是次数，$\mathbb{Z}$ 里是绝对值。凡是"有一个能严格下降的尺子 + 能做除法"的整环，都能做带余除法，统称欧几里得整环。你在本讲学到的不是"多项式的一个技巧"，而是"一整类结构共有的性质"。

---

七、自测（3–5 题，先做再看答案） #

1. 用竖式求 $z^3+3z^2-2$ 除以 $z^2-z+1$ 的商与余式，并验算。

2. 求 $p(z)=2z^3-3z^2+4z-5$ 除以 $z+1$ 的余数（不要做除法，用余数定理）。

3. 已知 $2$ 是 $p(z)=z^3-4z^2+z+6$ 的零点。用综合除法把 $p$ 完全分解成一次因式之积。

4. 判断：$z-1$ 是否整除 $z^5-2z^3+z+1$？说明理由。

5. 证明：在 $\mathbb{Z}[z]$ 中，$2z+1$ 除以 $2$ 不存在满足 $\deg r<\deg 2$ 的商与余式。这件事说明了什么？

答案（点开）

1. 补零：$p = z^3+3z^2+0z-2$。
第 1 步：$z^3\div z^2 = z$，减 $z(z^2-z+1)=z^3-z^2+z$，得 $4z^2-z-2$。
第 2 步：$4z^2\div z^2 = 4$，减 $4(z^2-z+1)=4z^2-4z+4$，得 $3z-6$。
$\deg(3z-6)=1<2$，停。故 $q=z+4$，$r=3z-6$。
验算：$(z^2-z+1)(z+4) = z^3+4z^2-z^2-4z+z+4 = z^3+3z^2-3z+4$，加 $r$ 得 $z^3+3z^2+0z-2$ ✓。

2. 由余数定理，余数 $=p(-1) = 2(-1)-3(1)+4(-1)-5 = -2-3-4-5 = -14$。
（注意 $\lambda=-1$，不是 $1$。写成 $p(1)=2-3+4-5=-2$ 是典型错误。）

3. 综合除法，$\lambda=2$，系数 $1,-4,1,6$：
落下 $1$；$1\times2=2$，$-4+2=-2$；$-2\times2=-4$，$1+(-4)=-3$；$-3\times2=-6$，$6-6=0$。
商 $q=z^2-2z-3$，余 $0$（验证了 $2$ 确是零点）。
再分解 $z^2-2z-3=(z-3)(z+1)$。故

$$p(z)=(z-2)(z-3)(z+1)$$

零点为 $2,3,-1$。

4. 不整除。由因式定理，$z-1$ 整除 $p$ 当且仅当 $p(1)=0$。
$p(1)=1-2+1+1=1\neq0$，故不整除；事实上余数就是 $1$。

5. 若存在，则 $2z+1 = 2q+r$ 且 $\deg r<\deg 2 = 0$。次数小于 $0$ 的多项式只有零多项式，
故 $r=0$，于是 $2q=2z+1$，即 $q=z+\frac12$。但 $q$ 必须是整系数多项式，$\frac12\notin\mathbb{Z}$，矛盾。
这说明带余除法要求系数在域中：$\mathbb{Z}$ 里 $2$ 没有倒数，"除以 $2$"这一步做不下去。
$\mathbb{F}[z]$（$\mathbb{F}$ 为 $\mathbb{R}$ 或 $\mathbb{C}$）才保证定理成立。

---

八、复习卡 #

项	内容
定理	$p,s\in\mathcal{P}(\mathbb{F})$，$s\neq0$ ⟹ 存在唯一 $q,r$：$p=sq+r$，$\deg r<\deg s$
"更小"的含义	用次数比：$\deg r<\deg s$（严格），不是 $r<s$
零多项式次数	$\deg 0=-\infty$；$-\infty<m$，$-\infty+m=-\infty$
$r=0$ 时	$\deg r=-\infty<\deg s$ 自动成立，无需单独讨论
$\deg p<\deg s$ 时	$q=0,\ r=p$（一步解决）
竖式每步	商项 $=\dfrac{a}{c}z^{k-m}$（$a,c$ 为首项系数），减去它乘 $s$，最高次被抹平
终止理由	次数每步至少降 1，最多 $\deg p-\deg s+1$ 步
余数定理	$p$ 除以 $z-\lambda$ 的余数 $=p(\lambda)$（仅一次除式）
因式定理	$p(\lambda)=0 \iff (z-\lambda)\mid p$；且 $\deg q=\deg p-1$
零点个数	$m$ 次多项式在 $\mathbb{F}$ 中至多 $m$ 个零点
唯一性证法	设两组解，相减得 $s(q_1-q_2)=r_2-r_1$，左次数 $\ge\deg s$、右 $<\deg s$，矛盾
线性代数证法	$\{1,z,\dots,z^{m-1},s,zs,\dots,z^{n-m}s\}$ 长度 $n+1=\dim\mathcal{P}_n$ 且无关 ⟹ 基；$p$ 的坐标给出 $r,q$
综合除法	只对 $z-\lambda$：抄系数、乘 $\lambda$、相加；末位是余数
符号陷阱	除以 $z+3$ 时上方写 $-3$
为什么要域	商项要除以除数首项系数，需其可逆；$\mathbb{Z}[z]$ 上不成立（$2z+1\div2$ 失败）
工程用途	CRC：$\mathbb{F}_2$ 上除以生成多项式取余，加减同为异或，硬件只需移位+异或

---

九、出处与延伸（可选，不影响阅读） #

• 本讲主要来源：带余除法定理（编号 4.9）在 PDF p118；它的证明用 $\mathcal{P}_n(\mathbb{F})$ 的基，见同一页。因式定理（零点对应一次因式，编号 4.6）、零点个数上界（4.8）、零多项式次数 $-\infty$ 的约定在 p116–p117。代数基本定理（4.12）及其"反复剥一次因式"的用法在 p118–p119，$\mathbb{C}$ 上与 $\mathbb{R}$ 上的完全分解（4.13）在 p120–p121。
• 本讲超出原文的部分（如实标注）：余数定理、长除法与综合除法的逐步算例、竖式与十进制的对照、CRC 与欧几里得算法/最大公因式，均属把原文一句话展开的教学材料，原文这几页未逐条给出。原文也没有「最大公因式」一节，那里是笔者的补充，读者可跳过。
• 想深挖时：任意一本讲"多项式环"或"欧几里得整环"的抽象代数教材都会把 $\mathbb{Z}$ 与 $\mathbb{F}[z]$ 并列处理，本讲 6.1 的说法在那些书里有完整版。数值计算方向可以查"综合除法 / Horner 法则"——综合除法与多项式求值的 Horner 算法是同一件事。
• 术语别名：带余除法 = 除法算式 = division algorithm（注意英文里的 algorithm 在数学文献中常指"存在唯一性定理"而非"计算步骤"，本讲开头已提醒）；商 = quotient；余式 = remainder；因式定理 = factor theorem。
• 一个可查的对照：$\mathbb{F}_2$ 上多项式除法的具体实现（生成多项式、余式、LFSR 结构）在通信原理类教材的"循环码"一章，CRC-32 的生成多项式是公开的标准值。