多項式の長除法

代数学において、多項式の長除法は、同じ次数またはそれ以下の次数の別の多項式で多項式を割るアルゴリズムであり、長除法と呼ばれるおなじみの算術的手法の一般化です。複雑な除算問題をより小さな問題に分割するため、手作業で簡単に実行できます。多項式の長除法は、多項式のユークリッド除法を実行するアルゴリズムです。2つの多項式A (被除数) とB (除数) から始めて、 B がゼロでない場合、商Qと余りRを生成します。

A = BQ + R、

そして、R = 0 であるか、 Rの次数がBの次数より低いかのいずれかである。これらの条件によって QとR は一意に定義される。R = 0となるのは、多項式AがB を因数として持つ場合のみである。したがって、長除法は、ある多項式が別の多項式を因数として持つかどうかを判定し、持つ場合は因数分解するための手段となる。

特に除数が一次多項式の場合、合成除法と呼ばれる簡略化された方法を用いる方が、記述量や計算量が少なく、より速く計算できる場合がある。

多項式の長除法は、多項式の係数が同じ体に属している場合に限り可能です。つまり、ゼロ以外の要素による除算は常に可能です。体の例としては、有理数、実数、複素数などがあります。

の割り算の商と余りを求めます。 ${\displaystyle (x^{3}-2x^{2}-4)}$配当金、${\displaystyle (x-3)}$除数。​

配当はまず次のように書き換えられます。

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

商と余りは、次のようにして求めることができます。

1. 被除数の最初の項を除数の最高次数（つまり、 xの最高次数を持つ項。この場合はx）で割ります。結果を横棒の上に置きます。${\displaystyle x^{3}\div x=x^{2}}$。

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

2. 除数に、先ほど得られた結果（最終的な商の最初の項）を掛けます。その結果を被除数の最初の2項の下に書きます。${\displaystyle x^{2}\cdot (x-3)=x^{3}-3x^{2}}$。

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

3. 先ほど得られた積を、元の被除数の該当する項から引きます（マイナス記号のあるものを引くことは、プラス記号のあるものを加えることと同じであることに注意してください）。そして、その結果を下に書きます。${\displaystyle \left(x^{3}-2x^{2}\right)-\left(x^{3}-3x^{2}\right)=-2x^{2}+3x^{2}=x^{2}}$次に、被除数から次の項を下ろします。

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

4. 前の３つの手順を繰り返しますが、今回は先ほど書いた２つの項を被除数として使用します。

   ${\displaystyle {\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を繰り返します。今回は、取り外すものは何もありません。

   ${\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 ) です。

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

または別の方法として

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

算術における長除法のアルゴリズムは、上記のアルゴリズムと非常によく似ています。ただし、変数x が(10 進数で) 特定の数値 10 に置き換えられ、さらにすべての係数が非負でなければならないという制約が加わります。

このアルゴリズムは擬似コードで次のように表すことができます。ここで+、、、−およびは×多項式の演算を表し、leadは入力引数として与えられた多項式の先頭項（最高次の項）を返す関数であり、はlead(remainder) / lead(denominator)先頭の2つの項を割って得られる多項式を返します。

関数の分子/分母は 分母が0でないことを条件とする 商 ← 0 余り ← 分子 // 各ステップで、分子 = 分母 × 商 + 余り 余りが 0 でない間、かつ次数(余り) ≥ 次数(分母)である間、 tmp ← lead(remainder) / lead(denominator) // 先頭項を割り算する 商 ← 商 + tmp 余り ← 余り − tmp × 分母 （商、余り）を返す

これはの場合にも同様に機能しますdegree(numerator) < degree(denominator)。この場合、結果は自明なものとなり(0, numerator)、while ループは決して実行されません。

このアルゴリズムは、上記の紙と鉛筆の方法を正確に説明しています。denominatorは「）」の左側に書かれquotient、 は水平線の上に項ごとに書かれ、tmpは各ループの繰り返しで商の最後の項を格納します。水平線の下の領域は、 の連続する値を計算して書き込むために使用されますremainder。

B ≠ 0 である任意の多項式のペア ( A , B )に対して、多項式の除算は商Qと余りRを与え、

${\displaystyle A=BQ+R,}$

また、R = 0 または degree( R ) < degree( B ) のいずれかである。さらに、( Q , R ) はこの性質を持つ唯一の多項式のペアである。

AとBから一意に定義された多項式QとRを得るプロセスは、ユークリッド除法（除法変換とも呼ばれる）と呼ばれます。したがって、多項式の長除法はユークリッド除法のアルゴリズムです。^{[ 1 ]}

除数が次数 1 の単項式多項式の場合、合成除法は筆算に代わる方法で、記述や計算が少なくて済みます。多項式を割るには、${\displaystyle f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\ldots +a_{1}x+a_{0}}$単線形多項式によって${\displaystyle x-c}$合成除法を用いると、係数を持つ 3 行配列が書き出される。${\displaystyle f(x)}$最上段。先頭の係数${\displaystyle a_{n}}$最下段に落ち、その積は${\displaystyle c}$2 行目の 2 番目の係数の下に書かれています${\displaystyle a_{n-1}}$これら2つを足し合わせ、その合計を3行目に置き、その積を${\displaystyle c}$下の2行目に書かれている${\displaystyle a_{n-2}}$など。例えば、分割用に生成された表は次のようになります。${\displaystyle x^{3}-12x^{2}+24}$による${\displaystyle x-3}$初期配置から、以下の手順で生成されます。 $${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\end{array}}&{\begin{array}{|rrrr}\ 1&-12&0&24\\&&&\\\hline \end{array}}\end{array}}}$$ 最初のステップでは $${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&24\\&3&&\\\hline 1&&&\\\end{array}}\end{array}}}$$ その後の加算と乗算のステップの結果は $${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&24\\&3&-27&\\\hline 1&-9&&\\\end{array}}\end{array}}}$$ このプロセスを繰り返すと、最終的な表が得られます。 $${\displaystyle {\begin{array}{cc}{\begin{array}{r}\\3\\\\\end{array}}&{\begin{array}{|rrrr}1&-12&0&24\\&3&-27&-81\\\hline 1&-9&-27&-57\\\end{array}}\end{array}}}$$ 分割を記録する${\displaystyle x^{3}-12x^{2}+24=(x-3)(x^{2}-9x-27)-57}$。

• 多項式の剰余定理
• ルッフィーニの法則
• ユークリッド領域
• グレブナー基礎
• 2つの多項式の最大公約数