多項式除法

多項式除法是代數中的一種算法，用一個同次或低次的多項式去除另一個多項式。它可以很容易地手算，因為它將一個相對複雜的除法問題分解成更小的一些問題。

範例

計算${\frac {x^{3}-12x^{2}-42}{x-3}}$

把被除式、除式按某個字母作降冪排列，缺項補零，寫成以下形式：

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

然後商和餘數可以這樣計算：

1. 將分子的第一項除以分母的最高次項（即次數最高的項，此處為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}}$

2. 將分母乘以首商，乘積寫在分子前兩項之下（同類項對齊）（$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}}$

3. 從分子的相應項中減去剛得到的乘積（消去相等項，把不相等的項結合起來），得到第一餘式，寫在下面。（$(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}}$

4. 把第一餘式當作新的被除式，重複前三步，得到次商與第二餘式（直到餘式為零或餘式的次數低於除式的次數時為止．被除式=除式×商式+餘式 ）

   ${\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}}$

5. 重複第四步，得到三商與第三餘式。餘式小於除式次數，運算結束。

   ${\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)的次數 < (P)的次數）。 然後，對某個商多項式$Q(x)$和餘數多項式 $R(x)$（(R)的係數 < (D)的係數），

${\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 臨時存儲；橫線以下的區域用於計算並寫下餘式的各個中間值。

參見

• 多項式餘數定理
• 綜合除法
• 歐幾里得整環
• Gröbner basis
• 多項式最大公因子

參見

• 餘式定理
• 綜合除法，一種更簡潔的歐氏多項式除法
• Ruffini定則
• 歐幾里得整環
• Gröbner基
• 最大公因式