多項式除法

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

範例

計算${\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}\quad x^{2}\\x-3{\overline {)x^{3}-12x^{2}+0x-42}}\end{matrix}}$

2. 將分母乘以首商，乘積寫在分子前兩項之下（同類項對齊）（$x^{2}\cdot (x-3)=x^{3}-3x^{2}$）。

   ${\begin{matrix}\quad x^{2}\\x-3{\overline {)x^{3}-12x^{2}+0x-42}}\\\qquad \;\;x^{3}-3x^{2}\end{matrix}}$

3. 從分子的相應項中減去剛得到的乘積（消去相等項，把不相等的項結合起來），得到第一餘式，寫在下面。（$(x^{3}-12x^{2})-(x^{3}-3x^{2})=-12x^{2}+3x^{2}=-9x^{2}$）然後，將分子的下一項「拿下來」。

   ${\begin{matrix}\quad x^{2}\\x-3{\overline {)x^{3}-12x^{2}+0x-42}}\\\qquad \;\;{\underline {x^{3}-3x^{2}}}\\\qquad \qquad \qquad \quad \;-9x^{2}+0x\end{matrix}}$

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

   ${\begin{matrix}\;\quad \quad \quad x^{2}-9x\\x-3{\overline {)x^{3}-12x^{2}+0x-42}}\\\;\;{\underline {\;\;x^{3}-\;\;3x^{2}}}\\\qquad \qquad \quad \;-9x^{2}+0x\\\qquad \qquad \quad \;{\underline {-9x^{2}+27x}}\\\qquad \qquad \qquad \qquad \qquad -27x-42\end{matrix}}$

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

   ${\begin{matrix}\quad \quad \quad \quad \quad \quad x^{2}-9x-27\\x-3{\overline {)x^{3}-12x^{2}+0x-42}}\\\;\;{\underline {\;\;x^{3}-\;\;3x^{2}}}\\\qquad \qquad \quad \;-9x^{2}+0x\\\qquad \qquad \quad \;{\underline {-9x^{2}+27x}}\\\qquad \qquad \qquad \qquad \qquad -27x-42\\\qquad \qquad \qquad \qquad \qquad {\underline {-27x+81}}\\\qquad \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$

這種方法特別適用於三次多項式，有時可以得到一個高次多項式的所有根。 例如，如果有理數根定理產生一個五次多項式的單個(有理)根，它可以被分解出來得到一個四次(四次)商，那麼一個四次多項式的根的黎曼顯式公式可以被用來找到五次多項式的其他四個根。 然而，沒有一般的方法可以用純代數方法求解一個五次曲線，參見 Abel-Ruffini 定理。

求多項式函數的切線

多項式長除法可以用來求在特定點 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 = x2-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。

循環冗餘校驗

循環冗餘校驗使用多項式除法的其餘部分來檢測傳輸信息中的錯誤。

偽代碼

算法可以用如下偽代碼表示，其中 + 、-和 × 表示多項式算術，和/表示兩項的簡單除法:

函数 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 的連續值。

帶餘除法

主條目：多項式長除法

對於 B ≠0的每一對多項式(A，B) ，多項式除法提供一個商 Q 和一個餘數 R，使得

$A=BQ+R,$

R = 0或學位(R) < 學位(B)。 而且(Q，R)是具有這一性質的唯一多項式對。

從 a 和 b 中得到唯一定義的多項式 Q 和 R 的過程稱為帶餘除法(有時是除法變換)。 因此，多項式長除法是帶餘除法的一種算法。

例子

多項式長除法

除以除數的商和餘數。$x^{3}-2x^{2}-4,$$x-3,$

紅利最初是這樣重寫的:

$x^{3}-2x^{2}+0x-4.$

然後，商和餘數可以確定如下:

1. 用除數的最大項除以紅利的第一項(即 x 的冪最大的項，在本例中是 x)。 將結果放在橫條上方(x3x = x2)。

   ${\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\x-3\ {\overline {)\ x^{3}-2x^{2}+0x-4}}\end{array}}$

2. 除數乘以剛剛得到的結果(最終商的第一項)。 在紅利的前兩項(x2 · (x-3) = x3-3x2)下寫出結果。

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

3. 從原始紅利的適當條件中減去剛得到的乘積(注意減去負號等於加上正號) ，然後在下面寫上結果((x3-2x2)-(x3-3x2) =-2x2 + 3x2 = x2)。 然後，「降低」下一期的股息。

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

4. 重複前面的三個步驟，但是這一次使用剛剛寫入的兩個術語作為紅利。

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

5. 重複步驟4。 這一次，沒有什麼可以「擊垮」。

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

條上面的多項式是商 q (x) ，剩下的數(5)是餘數 r (x)。

${x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}$

用於算術的長除法算法與上述算法非常相似，其中變量 x 被特定的數字10代替(以10為基數)。

多項式短除法

Blomqvist 的方法是上面長除法的縮寫。 這種筆和紙的方法使用與多項式長除法相同的算法，但是用心算來確定剩餘部分。 這需要較少的編寫，因此，一旦掌握了這種方法，可以成為一種更快的方法。

除法最初的寫法與長乘法相似，除數頂部為紅利，除數低於紅利。 商應該從左到右寫在條形圖的下面。

${\begin{matrix}\qquad \qquad x^{3}-2x^{2}+{0x}-4\\{\underline {\div \quad \qquad \qquad \qquad \qquad x-3}}\end{matrix}}$

除以除數的最大項(x3 x = x2)。 把結果放在橫條下面。 X3已被除去，沒有留下餘數，因此可以標記為使用反斜槓。 然後將結果 x2乘以除數 -3 = -3x2中的第二項。 通過減去-2x2-(- 3x2) = x2來確定部分餘數。 標記 -2x2，並將新的餘數 x2放在它上面。

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

餘數的最高項除以除數的最高項(x2 x = x)。 把結果(+ x)放在橫條下面。 X2已被除去，不留餘數，因此可以標記為已使用。 然後將結果 x 乘以除數 -3 = -3x 中的第二項。 通過減去0x-(- 3x) = 3x 來確定部分餘數。 將0x 標記為已使用，並將新的剩餘部分放在其上方3倍。

${\begin{matrix}\qquad \qquad \quad {\bcancel {x^{2}}}\quad 3x\\\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}}$

餘數的最大項除以除數的最大項(3xx = 3)。 把結果(+ 3)放在橫條下面。 3x 已被分割，沒有留下任何餘數，因此可以標記為使用。 然後將結果3乘以除數 -3 = -9中的第二項。 通過減去 -4-(-9) = 5來確定部分餘數。 標記 -4，並將新的剩餘5放在它上面。

${\begin{matrix}\quad \qquad \qquad \qquad {\bcancel {x^{2}}}\quad {\bcancel {3x}}\quad 5\\\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}}$

條形圖下面的多項式是商 q (x) ，剩下的數字(5)是餘數 r (x)。

參見

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

參見

• 多項式餘數定理
• 合成除法，一種更簡潔的歐氏多項式除法
• Ruffini 的規矩
• 歐幾里得整環
• 格羅布納基礎
• 多項式的最大公約數