多项式除法

多项式除法是代数中的一种算法，用一个同次或低次的多项式去除另一个多项式。它可以很容易地手算，因为它将一个相对复杂的除法问题分解成更小的一些问题。

范例
计算\frac{x^3 - 12x^2 - 42}{x-3}

把被除式、除式按某个字母作降幂排列，缺项补零，写成以下形式：

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

然后商和余数可以这样计算：

将分子的第一项除以分母的最高次项（即次数最高的项，此处为x），得到首商，写在横线之上(x^3\div x=x^2).
:
\begin{matrix}
x^2 \quad \quad \quad \quad \quad \\
x-3\overline{) x^3 - 12x^2 + 0x - 42}
\end{matrix}

将分母乘以首商，乘积写在分子前两项之下（同类项对齐）（x^2\cdot (x-3)=x^3 - 3x^2）。
:
\begin{matrix}
x^2 \quad \quad \quad \quad \quad \\
x-3\overline{) x^3 - 12x^2 + 0x - 42}\\
x^3 - 3x^2 \qquad\; \\
\end{matrix}

从分子的相应项中减去刚得到的乘积（消去相等项，把不相等的项结合起来），得到第一餘式，写在下面。（(x^3-12x^2)-(x^3-3x^2)=-12x^2+3x^2=-9x^2）然后，将分子的下一项“拿下来”。
:
\begin{matrix}
x^{2}\quad \quad \quad \quad \quad \\
x-3{\overline {)x^{3}-12x^{2}+0x-42}}\\
\underline{\;\;x^3 - \;\;3x^2\qquad \;}\\
\quad \;\quad-\;\; 9x^{2}+0x \;
\end{matrix}

把第一餘式当作新的被除式，重复前三步，得到次商與第二餘式（直到余式为零或余式的次数低于除式的次数时为止．被除式=除式×商式+余式 ）
:
\begin{matrix}
\ x^2 - 9x \quad\quad\quad \\
x-3\overline{) x^3 - 12x^2 + 0x - 42}\\
\underline{\;\;x^3 - \;\;3x^2\qquad \;}\\
\quad \;\quad-\;\; 9x^{2}+0x \;\\
\quad \;\;\quad\underline{-\;\; 9x^2 + 27x}\;\\
\qquad\qquad\qquad\qquad-27x - 42
\end{matrix}

重复第四步，得到三商與第三餘式。餘式小於除式次數，運算結束。
:
\begin{matrix}
\ x^2 - 9x \quad - 27\\
x-3\overline{) x^3 - 12x^2 + 0x - 42}\\
\underline{\;\;x^3 - \;\;3x^2\qquad \;}\\
\quad \;\quad-\;\; 9x^{2}+0x \;\\
\quad \;\;\quad\underline{-\;\; 9x^2 + 27x}\;\\
\qquad\qquad\qquad\qquad-27x - 42 \\
\qquad\qquad\qquad\qquad\underline{-27x + 81}\\
\qquad\qquad\qquad\qquad\qquad\;\; -123
\end{matrix}

横线之上的多项式即为商，而剩下的 (−123) 就是余数。

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

算数的长除法可以看做以上算法的一个特殊情形，即所有x被替换为10的情形。

除法变换
使用多项式长除法可以将一个多项式写成 除数-商 的形式（经常很有用）。 考虑多项式P(x), D(x) （(D)的次数 Q(x)和余数多项式 R(x)（(R)的系数 \frac{P(x)}{D(x)} = Q(x) + \frac{R(x)}{D(x)} \implies P(x) = D(x)Q(x) + R(x)
这种变换叫做除法变换，是从算数等式 {\mathrm{dividend} = \mathrm{divisor} \times \mathrm{quotient} + \mathrm{remainder}} 和被除數等於除數乘以商再加上餘數得到的。

应用
多项式的因式分解
有时某个多项式的一或多个根已知，可能是使用有理数根定理得到的。如果一个n次多项式 P(x)的一个根r已知，那么P(x) 可以使用多项式长除法因式分解为(x-r)Q(x)的形式，其中Q(x)是一个n-1次的多项式。简单来说，Q(x)就是长除法的商，而又知r是P(x)的一个根、余式必定为零。

相似地，如果不止一个根是已知的，比如已知r和s这两个，那么可以先从P(x)中除掉线性因子x-r得到Q(x)，再从Q(x)中除掉 x-s，以此类推。或者可以一次性地除掉二次因子x^2-(r+s)x+rs。

使用这种方法，有时超过四次的多项式的所有根都可以求得，虽然这并不总是可能的。例如，如果有理数根定理可以用来求得一个五次方程的一个（比例）根，它就可以被除掉以得到一个四次商式；然后使用四次方程求根的显式公式求得剩余的根。

寻找多项式的切线
多项式长除法可以用来在给定点上查找给定多项式的切线方程。 如果R(x)是\frac{P(x)}{(x-r)^2}的余式——也即，除以 x^2-2rx+r^2 ——那么在 x=r处P(x)的切线方程是y=R(x)，不论r是否是P(x)的根。

应用领域
分解多项式
有时一个多项式的一个或多个根已知，也许已经发现使用有理数根定理。如果n次多项式 P(x)的一个根r已知，那么多项式长除法可以用来将P(x)因子化为(x-r)Q(x)，其中Q(x)是 n-1次多项式。Q(x)是除法过程得到的商; 因为r是P(x)的根，所以余数必为零。

同样的，如果有几个根 r，s, . . . 在P(x)已知的情况下，可以划分出一个线性因子(x-r)得到Q(x)，然后再划分出(x-s)得到Q(x)等。或者，可以将二次因子从P(x)中分离出来，得到一个n-2次商。
(x-r)(x-s)=x^2-(r{+}s)x+rs

这种方法特别适用于三次多项式，有时可以得到一个高次多项式的所有根。 例如，如果有理数根定理产生一个五次多项式的单个(有理)根，它可以被分解出来得到一个四次(四次)商，那么一个四次多项式的根的黎曼显式公式可以被用来找到五次多项式的其他四个根。然而，没有一般的方法可以用纯代数方法求解一个五次曲线，参见阿貝爾-魯菲尼定理。

求多项式函数的切线
多项式长除法可以用来求在特定点x=r上与多项式P(x)定义的函数图相切的直线的方程。如果R(x)是P(x)除以(x - r)^2的余数，那么无论r 是否是多项式的根，x = r处的切线方程到函数y = P(x)的图是y = R(x)。

例子
在 x = 1 时，找到与下面曲线相切的直线的方程:

: y = x^3 - 12x^2 - 42.

首先将多项式除以(x-1)^2 = x^2-2x + 1:

:
\begin{array}{r}
x - 10\\
x^2-2x+1\ \overline{)\ x^3 - 12x^2 + 0x - 42}\\
\underline{x^3 - {\color{White}0}2x^2 + {\color{White}1}x} {\color{White} {} - 42}\\
-10x^2 - {\color{White}01}x - 42\\
\underline{-10x^2 + 20x - 10}\\
-21x - 32
\end{array}

切线是 y = -21x -32 。

循环冗余校验
循环冗余校验使用多项式除法的其余部分来检测传输信息中的错误。

伪代码
该算法可以用以下伪代码表示，其中 +、− 和 × 表示多项式运算，lead 是一个函数，用于返回给定多项式的首项（即次数最高的项），而 lead(余式) / lead(除式) 表示将两个首项相除所得到的单项式：

定义 函数 被除式 / 除式 执行
断言 除式 ≠ 0
商 ← 0
余式 ← 被除式 // 每一步都保持：被除式 = 除式 × 商 + 余式
当 余式 ≠ 0 且 次数(余式) ≥ 次数(除式) 时循环执行
tmp ← lead(余式) / lead(除式) // 将两个首项相除
商 ← 商 + tmp
余式 ← 余式 − tmp × 除式
返回 (商, 余式)

当被除式的次数小于除式的次数时，此算法同样适用；此时结果即为平凡解 (0, 被除式)，循环体不会被执行。
该算法精确地描述了上述的手算过程：将除式写在“)”的左侧；商的各项逐次写在横线上方；每次循环中的商的末项由变量 tmp 临时存储；横线以下的区域用于计算并写下余式的各个中间值。

参见
*多项式余数定理
*综合除法
*欧几里得整环
*
*

引用
参见

• 余式定理
• 综合除法，一种更简洁的欧氏多项式除法

*

• 欧几里得整环

*

• 最大公因式