查看“︁多项式除法”︁的源代码

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

==范例==

计算<math>\frac{x^3 - 12x^2 - 42}{x-3}</math>

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

:<math>\frac{x^3 - 12x^2 + 0x - 42}{x-3}</math>

然后[[商數|商]]和[[余数]]可以这样计算：

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

<li>将分母乘以首商，乘积写在分子前两项之下（同类项对齐）（<math>x^2\cdot (x-3)=x^3 - 3x^2</math>）。
:<math>
\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}
</math></li>
<li>从分子的相应项中减去刚得到的乘积（消去相等项，把不相等的项结合起来），得到第一餘式，写在下面。（<math>(x^3-12x^2)-(x^3-3x^2)=-12x^2+3x^2=-9x^2</math>）然后，将分子的下一项“拿下来”。 
:<math>
\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}
</math></li>

<li>把第一餘式当作新的被除式，重复前三步，得到次商與第二餘式（直到余式为零或余式的次数低于除式的次数时为止．被除式=除式×商式+余式 ）
:<math>
\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}
</math></li>

<li>重复第四步，得到三商與第三餘式。餘式小於除式次數，運算結束。
:<math>
\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}
</math></li>
</ol>

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

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

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

== 除法变换 ==
使用多项式长除法可以将一个多项式写成 除数-商 的形式（经常很有用）。 考虑多项式<math>P(x)</math>, <math>D(x)</math> （(''D'')的次数 < (''P'')的次数）。 然后，对某个商多项式<math>Q(x)</math>和余数多项式 <math>R(x)</math>（(''R'')的系数 < (''D'')的系数）， 
:<math>\frac{P(x)}{D(x)} = Q(x) + \frac{R(x)}{D(x)} \implies P(x) = D(x)Q(x) + R(x)</math>
这种变换叫做'''除法变换'''，是从算数等式 <math>{\mathrm{dividend} = \mathrm{divisor} \times \mathrm{quotient} + \mathrm{remainder}}</math><ref>{{cite book|author=S. Barnard|title=Higher Algebra|year=2008|publisher=READ BOOKS|isbn=1443730866|page=24}}</ref>  得到的。

==应用==

===多项式的因式分解===

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

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

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

===寻找多项式的切线===

多项式长除法可以用来在给定点上查找给定多项式的切线方程。<ref>Strickland-Constable, Charles, "A simple method for finding tangents to polynomial graphs", ''[[Mathematical Gazette]]'' 89, November 2005: 466-467.</ref> 如果<math>R(x)</math>是<math>\frac{P(x)}{(x-r)^2}</math>的余式——也即，除以<math>x^2-2rx+r^2</math>——那么在 <math>x=r</math>处<math>P(x)</math>的切线方程是<math>y=R(x)</math>，不论<math>r</math>是否是<math>P(x)</math>的根。

== 应用领域 ==

=== 分解多项式 ===

有时一个多项式的一个或多个根已知，也许已经发现使用有理数根定理。 如果 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次商。<math>(x-r)(x-s)=x^2-(r{+}s)x+rs</math>

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

=== 求多项式函数的切线 ===

多项式长除法可以用来求在特定点 x = r 上与多项式 p (x)定义的函数图相切的直线的方程。如果 R (x)是 P (x)除以(x-r)2的余数，那么无论 r 是否是多项式的根，x = r 处的切线方程到函数 y = P (x)的图是 y = R (x)。<ref>Strickland-Constable, Charles, "A simple method for finding tangents to polynomial graphs", ''[[Mathematical Gazette]]'' 89, November 2005: 466-467.</ref>

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

: <math>y = x^3 - 12x^2 - 42.</math>

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

: <math>
\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}
</math>

切线是 y =-21x-32。

=== 循环冗余校验 ===

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

== 伪代码 ==

算法可以用如下伪代码表示，其中 + 、-和 × 表示多项式算术，和/表示两项的简单除法:

 函数 n/d 在每个步长 n = d × q + r 时，要求 d ≠0 q →0 r → n//
 
     当 r ≠0且度(r)≥度(d)时，t → lead (r)/lead (d)//除以前导项 q → q + t r → r-t × d
 
     回报率(q，r)

当度(n) < 度(d)时，这种方法同样有效; 在这种情况下，结果只是平凡的(0，n)。

这个算法准确地描述了上面的纸和铅笔法: d 写在“)”的左边; q 写在水平线上，一个术语接着一个术语，最后一个术语是 t 的值; 水平线下的区域用来计算和写下 r 的连续值。

== 带余除法 ==

{{Main|多项式长除法}}对于 B ≠0的每一对多项式(A，B) ，多项式除法提供一个商 Q 和一个余数 R，使得 

: <math>A=BQ+R,</math>

R = 0或学位(R) < 学位(B)。 而且(Q，R)是具有这一性质的唯一多项式对。

从 a 和 b 中得到唯一定义的多项式 Q 和 R 的过程称为带余除法(有时是除法变换)。 因此，多项式长除法是带余除法的一种算法。<ref>{{Cite book|last=S. Barnard|title=Higher Algebra|year=2008|publisher=READ BOOKS|isbn=978-1-4437-3086-0|page=24}}<cite class="citation book cs1" data-ve-ignore="true" id="CITEREFS._Barnard2008">S. Barnard (2008). ''Higher Algebra''. READ BOOKS. p.&nbsp;24. [[国际标准书号|ISBN]]&nbsp;[[特别: 书籍来源/978-1-4437-3086-0|<bdi>978-1-4437-3086-0</bdi>]].</cite></ref>

== 例子 ==

=== 多项式长除法 ===
除以除数的商和余数。<math>x^3 - 2x^2 - 4,</math><math>x-3,</math>

红利最初是这样重写的:

: <math>x^3 - 2x^2 + 0x - 4.</math>

然后，商和余数可以确定如下:

#用除数的最大项除以红利的第一项(即 x 的幂最大的项，在本例中是 x)。 将结果放在横条上方(x3x = x2)。
#: <math>
\begin{array}{l}
{\color{White} x-3\ )\ x^3 - 2}x^2\\
x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}
\end{array}
</math>
#除数乘以刚刚得到的结果(最终商的第一项)。 在红利的前两项(x2 · (x-3) = x3-3x2)下写出结果。
#: <math>
\begin{array}{l}
{\color{White} x-3\ )\ x^3 - 2}x^2\\
x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\
{\color{White} x-3\ )\ } x^3 - 3x^2
\end{array}
</math>
#从原始红利的适当条件中减去刚得到的乘积(注意减去负号等于加上正号) ，然后在下面写上结果((x3-2x2)-(x3-3x2) =-2x2 + 3x2 = x2)。 然后，“降低”下一期的股息。
#: <math>
\begin{array}{l}
{\color{White} x-3\ )\ x^3 - 2}x^2\\
x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\
{\color{White} x-3\ )\ } \underline{x^3 - 3x^2}\\
{\color{White} x-3\ )\ 0x^3} + {\color{White}}x^2 + 0x
\end{array}
</math>
#重复前面的三个步骤，但是这一次使用刚刚写入的两个术语作为红利。
#: <math>
\begin{array}{r}
 x^2 + {\color{White}1}x {\color{White} {} + 3}\\
 x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\
 \underline{x^3 - 3x^2 {\color{White} {} + 0x - 4}}\\
 +x^2 + 0x {\color{White} {} - 4}\\
 \underline{+x^2 - 3x {\color{White} {} - 4}}\\
 +3x - 4\\
\end{array}
</math>
#重复步骤4。 这一次，没有什么可以“击垮”。
#: <math>
\begin{array}{r}
 x^2 + {\color{White}1}x + 3\\
 x-3\ \overline{)\ x^3 - 2x^2 + 0x - 4}\\
 \underline{x^3 - 3x^2 {\color{White} {} + 0x - 4}}\\
 +x^2 + 0x {\color{White} {} - 4}\\
 \underline{+x^2 - 3x {\color{White} {} - 4}}\\
 +3x - 4\\
 \underline{+3x - 9}\\
 +5
\end{array}
</math>

条上面的多项式是商 q (x) ，剩下的数(5)是余数 r (x)。

: <math>{x^3 - 2x^2 - 4} = (x-3)\,\underbrace{(x^2 + x + 3)}_{q(x)}  +\underbrace{5}_{r(x)}</math>

用于算术的长除法算法与上述算法非常相似，其中变量 x 被特定的数字10代替(以10为基数)。

=== 多项式短除法 ===
Blomqvist 的方法是上面长除法的缩写。<ref>Archived at [https://ghostarchive.org/varchive/youtube/20211211/Ad16hxs809I Ghostarchive] and the {{Citation|title=Blomqvist's division: the simplest method for solving divisions?|url=https://www.youtube.com/watch?v=Ad16hxs809I&gl=US&hl=en|language=en|access-date=2019-12-10|archive-date=2020-04-01|archive-url=https://web.archive.org/web/20200401062354/https://www.youtube.com/watch?v=Ad16hxs809I&gl=US&hl=en|dead-url=unfit}}: {{Citation|title=Blomqvist's division: the simplest method for solving divisions?|url=https://www.youtube.com/watch?v=Ad16hxs809I|language=en|access-date=2019-12-10}}<cite class="citation cs2" data-ve-ignore="true">[https://www.youtube.com/watch?v=Ad16hxs809I ''Blomqvist's division: the simplest method for solving divisions?''] {{Wayback|url=https://www.youtube.com/watch?v=Ad16hxs809I |date=20220724001208 }}<span class="reference-accessdate">, retrieved <span class="nowrap">2019-12-10</span></span></cite></ref> 这种笔和纸的方法使用与多项式长除法相同的算法，但是用心算来确定剩余部分。 这需要较少的编写，因此，一旦掌握了这种方法，可以成为一种更快的方法。

除法最初的写法与长乘法相似，除数顶部为红利，除数低于红利。 商应该从左到右写在条形图的下面。

: <math>\begin{matrix} \qquad \qquad x^3-2x^2+{0x}-4 \\ \underline{ \div \quad \qquad \qquad \qquad \qquad  x-3 }\end{matrix}</math>

除以除数的最大项(x3 x = x2)。 把结果放在横条下面。 X3已被除去，没有留下余数，因此可以标记为使用反斜杠。 然后将结果 x2乘以除数 -3 = -3x2中的第二项。 通过减去-2x2-(- 3x2) = x2来确定部分余数。 标记 -2x2，并将新的余数 x2放在它上面。

: <math>\begin{matrix} \qquad x^2 \\ \qquad \quad \bcancel{x^3}+\bcancel{-2x^2}+{0x}-4 \\ \underline{ \div \qquad \qquad \qquad \qquad \qquad  x-3 }\\x^2 \qquad \qquad \end{matrix}
</math>

余数的最高项除以除数的最高项(x2 x = x)。 把结果(+ x)放在横条下面。 X2已被除去，不留余数，因此可以标记为已使用。 然后将结果 x 乘以除数 -3 = -3x 中的第二项。 通过减去0x-(- 3x) = 3x 来确定部分余数。 将0x 标记为已使用，并将新的剩余部分放在其上方3倍。

: <math>\begin{matrix} \qquad \qquad \quad\bcancel{x^2} \quad3x\\ \qquad \quad \bcancel{x^3}+\bcancel{-2x^2}+\bcancel{0x}-4 \\ \underline{ \div \qquad \qquad \qquad \qquad \qquad  x-3 }\\x^2 +x \qquad \end{matrix}
</math>

余数的最大项除以除数的最大项(3xx = 3)。 把结果(+ 3)放在横条下面。 3x 已被分割，没有留下任何余数，因此可以标记为使用。 然后将结果3乘以除数 -3 = -9中的第二项。 通过减去 -4-(-9) = 5来确定部分余数。 标记 -4，并将新的剩余5放在它上面。

: <math>\begin{matrix} \quad \qquad \qquad \qquad\bcancel{x^2} \quad \bcancel{3x} \quad5\\
\qquad \quad \bcancel{x^3}+\bcancel{-2x^2}+\bcancel{0x}\bcancel{-4} \\
\underline{ \div \qquad \qquad \qquad \qquad \qquad  x-3 }\\
x^2 +x +3\qquad \end{matrix}
</math>

条形图下面的多项式是商 q (x) ，剩下的数字(5)是余数 r (x)。

==参见==
*[[多项式余数定理]]
*[[综合除法]]
*[[欧几里得整环]]
*{{tsl|en|Gröbner basis|Gröbner basis}}
*{{tsl|en|Greatest common divisor of two polynomials|多项式最大公因子}}

==引用==
<references/>

{{多项式}}

{{DEFAULTSORT:Polynomial Long Division}}
[[Category:多项式]]
[[Category:除法]]

== 参见 ==

* [[Polynomial remainder theorem|多项式余数定理]]
* 合成除法，一种更简洁的欧氏多项式除法
* [[Ruffini's rule|Ruffini 的规矩]]
* [[Euclidean domain|欧几里得整环]]
* [[Gröbner basis|格罗布纳基础]]
* [[Greatest common divisor of two polynomials|多项式的最大公约数]]