多項式の長除算

代数学において、多項式長除法は、多項式を同じ次数またはより低い次数の別の多項式で除算するアルゴリズムであり、長除法と呼ばれるよく知られた算術技法の一般化バージョンです。複雑な除算問題を小さな問題に分割するため、手作業で簡単に実行できます。合成除法と呼ばれる短縮バージョンを使用すると、記述量と計算量が少なくなり、処理が速くなる場合があります。別の短縮法として、多項式短縮除法 (Blomqvist 法) があります。

多項式長除法は、多項式のユークリッド除法を実装するアルゴリズムであり、2つの多項式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 ) で割ることで因数分解できます。

被除数 を除数で割ったときの商と余りを求めます 。 ${\displaystyle (x^{3}-2x^{2}-4)}$${\displaystyle (x-3)}$

まず、被除数は次のように書き直されます。

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

商と余りは次のようにして決定できます。

1. 被除数の最初の項を除数の最大の項（xの最大のべき乗を持つ項、この場合はx）で割ります。結果をバーの上に置きます（x ³ ÷ x = x ²）。

   ${\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 つの項の下に記入します（x ² · ( x − 3) = x ³ − 3 x ²）。

   ${\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. 得られた積を元の被除数の適切な項から減算し (マイナス記号のあるものを引くことはプラス記号のあるものを加えることと同じであることに注意してください)、その結果を下に記入します。( x ³ − 2 x ² ) − ( x ³ − 3 x ² ) = −2 x ² + 3 x ² = x ² 次に、被除数から次の項を「下げます」。

   ${\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. 前の 3 つの手順を繰り返しますが、今回は被除数として先ほど書いた 2 つの項を使用します。

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

算術の長除算アルゴリズムは上記のアルゴリズムと非常によく似ており、変数x が(基数 10 で) 特定の数値 10 に置き換えられます。

Blomqvist 法^[1]は、上記の長除法の簡略版です。このペンと紙を使った方法は、多項式長除法と同じアルゴリズムを使用しますが、余りを求めるために暗算を使用します。この方法では、書く量が少なくて済むため、一度習得すればより高速な方法になります。

除算は、最初は長い乗算と同じように、被除数を上に、除数をその下に書きます。商は、バーの下に左から右に書きます。

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

被除数の最初の項を除数の最大の項で割ります ( x ³ ÷ x = x ² )。結果をバーの下に置きます。x ^{3 は}余りを残さずに割られているため、使用済みとして取り消し線で消せます。次に、結果x ^{2に除数 −3 = −3} x ²の 2 番目の項を掛けます。 −2 x ² − (−3 x ² ) = x ²を減算して部分余りを求めます。 −2 x ^{2 を}使用済みとしてマークし、新しい余り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}}}$

余りの最高項を除数の最高項で割ります ( x ² ÷ x = x )。結果 (+x) をバーの下に置きます。x ^{2 は}割り切れて余りがないため、使用済みとしてマークできます。結果xに除数の 2 番目の項 -3 = -3 xを掛けます。0 x - (-3 x ) = 3 xを減算して部分余りを決定します。0 x を使用済みとしてマークし、新しい余り 3 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 \qquad \qquad \qquad x-3}}\\x^{2}+x\qquad \end{matrix}}}$

余りの最高項を除数の最高項で割ります (3x ÷ x = 3)。結果 (+3) をバーの下に置きます。3x は余りがないので、使用済みとしてマークできます。結果 3 に除数の 2 番目の項 -3 = -9 を掛けます。-4 - (-9) = 5 を減算して部分余りを求めます。-4 を使用済みとしてマークし、新しい余り 5 をその上に置きます。

${\displaystyle {\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 )である。

このアルゴリズムは、次のように疑似コードで表すことができます。ここで、-、× は多項式演算を表し、+、/ は 2 つの項の単純な加算と除算を表します。

関数n / dは
    d ≠ 0 が必要
    q ← 0
    r ← n // 各ステップで n = d × q + r

    r ≠ 0かつdegree(r) ≥ degree(d)の場合、
        t ← lead(r) / lead(d) // 先頭の項を割る
        q ← q + t
        r ← r − t × d

    （q, r）
を返す

これは、degree( n )<degree( d )の場合でも同様に機能します。その場合、結果は単なる(0, n )になります。

このアルゴリズムは、まさに上記の紙と鉛筆による方法を記述します。つまり、dは「)」の左側に書き込まれ、q は水平線の上に項ごとに書き込まれ、最後の項はtの値になります。水平線の下の領域は、 rの連続する値を計算して書き留めるために使用されます。

B ≠ 0となる多項式（ A、B ）のペアに対して、多項式の割り算は商Qと余りRを与え、

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

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

AとBから一意に定義された多項式QとRを得るプロセスはユークリッド除算（除算変換と呼ばれることもある）と呼ばれる。多項式長除算はユークリッド除算のアルゴリズムである。 ^[2]

多項式の 1 つ以上の根がわかっている場合があり、これはおそらく有理根定理を使用して求められます。n次多項式P ( x )の1 つの根r がわかっている場合は、多項式の長除法を使用してP ( x ) を( x − r ) Q ( x )の形式に因数分解できます。ここで、Q ( x ) はn − 1 次多項式です。 Q ( x ) は単に除算プロセスから得られる商です。rはP ( x )の根であることがわかっているため、余りは 0 になることがわかります。

同様に、 P ( x )の複数の根r、s、…がわかっている場合は、線形因子( x − r )を割ってQ ( x )を取得し、次に( x − s )をQ ( x )から割るなどすることができます。あるいは、2次因子をP ( x )から割ってn −2次の商を取得することもできます。${\displaystyle (x-r)(x-s)=x^{2}-(r{+}s)x+rs}$

この方法は特に 3 次多項式に有効で、高次多項式のすべての根が得られることもあります。たとえば、有理根定理により5 次多項式の 1 つの (有理) 根が得られる場合、それを因数分解して 4 次 (4 次) の商を得ることができます。その後、 4 次多項式の根の明示的な公式を使用して、5 次多項式の他の 4 つの根を求めることができます。ただし、純粋に代数的な方法で 5 次多項式を解く一般的な方法はありません。アーベル・ルフィニの定理を参照してください。

多項式の長除法は、多項式P ( x ) で定義される関数のグラフの特定の点x = rにおける接線の方程式を求めるのに使用できます。^[3] R ( x ) がP ( x ) を( x – r ) ²で割った余りである場合、 r が多項式の根であるかどうかに関係なく、関数y = P ( x )のグラフに対するx = rにおける接線の方程式は y = R ( x )です。

次の曲線に接する直線の方程式を求めなさい ${\displaystyle y=(x^{3}-12x^{2}-42)}$

で：${\displaystyle x=1}$

まず、多項式を次のように割ります。 ${\displaystyle (x-1)^{2}=(x^{2}-2x+1)}$

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

接線は ${\displaystyle y=(-21x-32)}$

巡回冗長検査では、多項式除算の剰余を使用して、送信されたメッセージのエラーを検出します。

• 多項式剰余定理
• 合成除算、ユークリッド多項式除算をより簡潔に実行する方法
• ルフィニの法則
• ユークリッド領域
• グレブナー基底
• 2つの多項式の最大公約数