Pebble Coding

ソフトウェアエンジニアによるIT技術、数学の備忘録

多項式の割り算、商と余り

多項式の割り算、商と余りの求め方をみていきます。 1変数xの2つの多項式A(x), B(x)を考えます。多項式の係数は全て整数とします。
次数の大きい方をA(x), 次数の少ない方をB(x)とし、
ここでは次数の少ない方の多項式の最大次数の係数は1としておきます。
余りは次数の少ない方の最大次数より小さい最大次数の多項式となります。
例をみていきます。
 A(x) = x^{9} -x, B(x) = x^{3} + 2x + 1とします。
 x^{9} - x = x^{6} (x^{3} + 2x + 1) - 2 x^{7} - x^{6} - x
 -2 x^{7} - x^{6} - x = -2 x^{4} (x^{3} + 2x + 1) + 4x^{5} + 2x^{4} - x^{6} -x
 -x^{6} + 4x^{5} + 2x^{4} -x = -x^{3}(x^{3} + 2x + 1) + 2x^{4} + x^{3} + 4x^{5} + 2x^{4} -x
 4x^{5} + 4x^{4} + x^{3} -x = 4x^{2}(x^{3} + 2x + 1) - 8x^{3} - 4x^{2} + 4x^{4} + x^{3} - x
 4x^{4} - 7x^{3} - 4x^{2} -x = 4x(x^{3} + 2x + 1) - 8x^{2} -4x -7x^{3} -4x^{2} -x
 -7x^{3} - 12x^{2} - 5x = -7(x^{3} + 2x + 1) + 14x + 7 - 12x^{2} - 5x
 -12x^{2} + 9x + 7

余りが -12x^{2} + 9x + 7 と求まりました。
商は x^{6} - 2 x^{4} - x^{3} + 4x^{2} + 4x - 7であることが読み取れます。
このように多項式でも商と余りが定義できるということは、最大公約式も求めることができそうです。

実際、定数倍が出る以外は整数のユークリッドの互除法が多項式でも利用できることが知られています。

http://www.math.nagoya-u.ac.jp/~miyachi/courses/2W11_files/miyachi-2W11-05.pdf

ここでは次数の少ない方の多項式の最大次数の係数を1としましたが、多項式の係数を整数ではなく素体とすれば、
割り算もできるので、次数の係数が任意の数で商、余りが求められます。