多项式除法（代数） 学习笔记

注意，本文与「快速数论变换 NTT」无关，是一种代数计算技巧

多项式除法是代数中的一种算法，可以快速手算出一个同次或低次的多项式去除另一个多项式的结果。

事实上，小学学的竖式除法就是该算法在 $x = 10$ 时的特殊求解方法。

例：考虑计算

$$\dfrac{x^3-12 x^2-42}{x-3}$$

解：

1. 首先把分子和分母均以降幂排列，缺项补零

   $$\frac{x^3-12 x^2+0 x-42}{x-3}$$

2. 将分子的第一项除以分母的最高次项（即 $x^3 \div x = x^2$）

   

3. 将分母乘以首商，乘积写在分子前两项（同类项对齐）（$x^2 \cdot(x-3)=x^3-3 x^2$）

   

4. 从分子相应项中减去刚刚得到的乘积，得到第一余式 $-9x^2$ 并写在下方，然后将分子的下一次项拿出来

   

5. 接下来就把 $-9x^2 + 0x$ 当作新的被除式，重复前三步

   

6. 最后得到下式，余式小于除式次数，运算结束

   

7. 横线之上的多项式即为商，而剩下的 $-123$ 就是余数，则

   $$\frac{x^3-12 x^2-42}{x-3}=\underbrace{x^2-9 x-27}_{q(x)} \underbrace{-\frac{123}{x-3}}_{r(x) / g(x)}$$

---

参考文献：

[1] 多项式除法 - 维基百科，自由的百科全书