多项式長除法 - 百科事典

代数において、多项式の長除法は、同じ度合いまたはそれ以下の度合いの別の多项式で除されるためのアルゴリズムであり、馴染みのある算術技術である長除法の一般化版です。これを行うことは手で簡単に行えます。なぜなら、それが別々の複雑な除法問題をより小さな問題に分割するからです。時には略式版である合成除法を使用することで、より速く、書き込みが少なく、計算も少なくできます。もう一つの略式方法は、ポリノムの短除法（Blomqvistの方法）です。

多项式の長除法は、二つのポリノムA（被除数）とB（除数）から、Bが0でない場合、商Qと余剰Rを生成するためのユークリッド除法を実装するアルゴリズムです。これにより、A = BQ + R、そしてR = 0またはRの度合いがBの度合いより低いことが示されます。これらの条件はQとRをユニークに定義し、これはQとRがそれらを計算する方法に依存しないことを意味します。

余剰R = 0が発生するのは、AがBを因数として持つ場合のみです。したがって、長除法は、一つのポリノムが他のポリノムを因数として持つかどうかをテストする手段であり、それがそうである場合、それを因数分解するための手段です。例えば、Aの根rが既知であれば、Aを(x - r)で除すことで因数分解できます。

例


= 多項式の長除法 =
以下の被除数を除数で除す商と余剰を求めます：


(
x
3
−
2
x
2
−
4
)

{\displaystyle (x^{3}-2x^{2}-4)}

、除数

(
x
−
3
)

{\displaystyle (x-3)}

、を除します。

まず、被除数を以下のように書き直します：


x
3
−
2
x
2
+
0
x
−
4.

{\displaystyle x^{3}-2x^{2}+0x-4.}

次に、商と余剰を以下のように決定します：

被除数の最初の項を除数の最高項で除します（つまり、xの最高の次の項であるx）。結果をバーの上に置きます（x3 ÷ x = x2）。


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

結果を得た除数で乘算します（商の最初の項であるx2 · (x − 3) = x3 − 3x2）。被除数の最初の二つの項の下に結果を書きます。


x
−
3
)
x
3
−
2
x
2
−
4
¯
{\displaystyle {\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}}}

得た積から被除数の適切な項から引き算します（マイナスのものを引き算することはプラスのものを加算することに等しいことに注意して）、結果を下に書きます（x3 − 2x2） − （x3 − 3x2） = −2x2 + 3x2 = x2。

次に、被除数から次の項を「引き下ろ」ます。


x
−
3
)
x
3
−
2
x
2
−
4
¯
{\displaystyle {\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}}}

前の三つのステップを繰り返しますが、今度は引き下ろす項を使用します。


x
2
+
1
x
+
3
{\displaystyle x^{2}+{\color {White}1}x+3}

、除数

x
−
3
)
x
3
−
2
x
2
−
4
¯
{\displaystyle {\begin{array}{l}{\color {White}x-3\ )\ x^{3}-2}x^{2}\\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}}}

これらのステップを繰り返します。今度は「引き下ろす」ものがありません。


x
2
+
1
x
+
3
{\displaystyle x^{2}+{\color {White}1}x+3}

、除数

x
−
3
)
x
3
−
2
x
2
−
4
¯
{\displaystyle {\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
−
2
x
2
−
4
=
(
x
−
3
)
⏟
q
(
x
)
+
⏟
5
r
(
x
)
{\displaystyle {x^{3}-2x^{2}-4}=(x-3)\,\underbrace {(x^{2}+x+3)} _{q(x)}+\underbrace {5} _{r(x)}}

算術の長除法アルゴリズムは、変数xが10の特定の数（10進法）に置き換えられた上記のアルゴリズムと非常に似ています。

多項式の短除法 =
Blomqvistの方法は上記の長除法の略式版です。この手書きの方法は、ポリノムの長除法と同じアルゴリズムを使用しますが、余剰を決定するために心の計算を使用します。これはより少ない書き込みが必要であり、一度マスターすればより速い方法になります。

まず、除法は被除数が上、除数が下に書かれた長倍算の似た方法で書かれます。商はバーの下から左から右に書かれます。


x
3
−
2
x
2
+
0
x
−
4
÷
x
−
3
_
{\displaystyle {\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が上に置かれます。


x
2
{\displaystyle {\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）。バーの下に結果を置きます。x2は除され、残りがなく、したがって使用済みとマークできます。結果xは除数の第二項（-3）で乗算され、-3xと結果が得られます。部分余剰は0x − （-3x） = 3xで決定されます。0xは使用済みとマークされ、新しい余剰3xが上に置かれます。


x
2
+
x
{\displaystyle {\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