配布プリント

計算機数学演習 A 2014.6.6. 多項式のユークリッドの互除法
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
多項式に対するユークリッドの互除法
1
1 変数の多項式についても, 整数と同様に割り算を行うことができた. 約元や公約元や最大公約元なども, 整数と同様
に定義することができる.
例 1. 多項式 f = x3 + x2 + x + 2 を多項式 g = x + 1 で割り算した時, 商は x2 + 1, 余りは 1 である. 割られる元と割
る元の関係式は, f = (x2 + 1)g + 1 となる.
例 2. 多項式 f = (x + 1)2 (x + 2) と g = (x + 1)(x + 2) について, h = (x + 1)(x + 2) は f, g を割り切るので, f と g の
公約元である. さらに, h は f と g の公約元の中で次数が最大のものなので, f と g の最大公約元 GCD(f, g) である.
問題 3. 多項式 f = x4 + x3 + x2 + x + 1 を g = x2 + 2 で割った商と余りを計算せよ.
Asir において, 多項式の割り算の商と余りを求める関数として, sdiv と srem がある.
Asir における多項式の割り算
[2010] F=x^4+x^3+x^2+x+1;
x^4+x^3+x^2+x+1
[2011] G=x^2+2;
x^2+2
[2012] sdiv(F, G);
F を G で割った商
x^2+x-1
[2013] srem(F, G);
F を G で割った余り
-x+3
定理 4 (ユークリッドの互除法の原理 (多項式)). 多項式 f, g について, f を g で割った商を q とし, 余りを r とする.
（すなわち, f = qg + r
(deg r ≤ deg g) が成り立つ.）この時, GCD(f, g) = GCD(g, r) が成り立つ.
例 5. GCD(x3 + 9x2 + 26x + 24, x3 + 7x2 + 14x + 8) を計算する.
x3 + 9x2 + 26x + 24 =1 · (x3 + 7x2 + 14x + 8) + (2x2 + 12x + 16)
)
(
1
1
x+
· (2x2 + 12x + 16) + 0
x3 + 7x2 + 14x + 8 =
2
2
だから,
GCD(x3 + 9x2 + 26x + 24, x3 + 7x2 + 14x + 8) = GCD(x3 + 7x2 + 14x + 8, 2x2 + 12x + 16) = 2x2 + 12x + 16
問題 6. GCD(x6 − 1, x4 − 1) を手で計算してみよ.
アルゴリズム 7 (ユークリッドの互除法 (多項式)).
入力 : 多項式 f, g, 出力 : GCD(f, g)
1. g ̸= 0 である限り, 2, 3, 4 を続ける.
2.
r ← (f を g で割った余り)
3.
f ← g,
4.
1 へ.
g←r
5. f を出力.
1
プログラム 8 (ユークリッドの互除法 (多項式) のプログラム). Asir で上のアルゴリズムを実装すると次のようになる.
p gcd.rr
def p_gcd(F, G)
{
while (G !=
R =
F =
G =
}
return F;
}
end$
0) {
srem(F, G);
G;
R;
問題 9. 上のプログラムを使って, GCD(x6 − 14x4 + 49x2 − 36, x6 − 6x5 + 11x4 − 5x3 − 6x2 + 11x − 6) を計算せよ.
多項式の最大公約元の応用として, 次のような問題を考える.
例 10. 2 つの多項式 f = x3 − 10x2 + 29x − 20 と g = x4 − 11x3 + 39x2 − 49x + 29 が与えられているとする. 方程
式 f = 0 と g = 0 について, どちらの方程式の解 (共通解) にもなっているものを求めたい. 多項式 f, g の最大公約元
GCD(f, g) = x − 1 となる. 実は x − 1 = 0 の解 x = 1 がその共通解になる.
問題 11. 方程式 6x3 − 5x2 + x = 0 と 60x3 − 71x2 + 26x − 3 = 0 の共通解を求めよ.
問題 12. 方程式 x3 − 6x2 + 11x − 6 = 0 と 24x3 − 26x2 + 9x − 1 = 0 の共通解を求めよ.
上のようにそれぞれの方程式の解はわからなくても, 最大公約元が計算できれば, 共通解は計算することができる.
例 13. 多項式 f = (x−1)(x−2)2 (x−3)3 を考える. 方程式 f = 0 の解は 1, 2, 3 であるが, 2, 3 は重複解である. 多項式 f
を x で微分したもの f ′ = (x−2)(x−3)2 (6x2 −22x+11) を考える. 多項式 f, f ′ の最大公約元 GCD(f, f ′ ) = (x−2)(x−3)2
であり, (x − 2)(x − 3)2 = 0 の解と方程式 f = 0 の重複解と対応する.
問題 14. 多項式 f = x5 − 10x4 + 38x3 − 68x2 + 57x − 18 とする. 方程式 f = 0 の重複解を求めよ. （Asir において, x に
ついての微分を計算するには, コマンド diff を用いる. 例えば, (x3 + x2 + 1)′ を計算したい場合, diff(x^3+x^2+1, x);
と打ち込めばよい.）
問題 15. 多項式 f = (x − 1)3 (x − 2)4 (x − 3)5 とする.
f
= (x − 1)(x − 2)(x − 3)
GCD(f, f ′ )
になることを確かめよ. （多項式の無平方分解）（Asir において, 有理関数は自動的には約分されない. 有理関数を約分
するには, コマンド red を用いる. 例えば, 有理関数
x2
x3
を約分したい場合, red(x^2/x^3); と打ち込めばよい.）
2

Download Report