計算機数学演習 A 2014.5.30. 拡張ユークリッドの互除法
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
1
拡張ユークリッドの互除法
例 1. 1 次方程式 41x + 29y = 1 の整数解 x, y を計算せよ. 41, 29 に対して, ユークリッドの互除法を行えば次のような
計算過程になる.
41 =1 · 29 + 12
12 =41 − 1 · 29
29 =2 · 12 + 5
5 =29 − 2 · 12 = 2 · 41 + 3 · 29
12 =2 · 5 + 2
2 =12 − 2 · 5 = 5 · 41 − 7 · 29
5 =2 · 2 + 1
1 =5 − 2 · 2 = −12 · 41 + 17 · 29
2 =2 · 1 + 0
よって x = −12, y = 17.
問題 2. 1 次方程式 17x + 13y = 1 の整数解 x, y を計算せよ.
一般に, 整数 a, b に対して, ax + by = GCD(a, b) を満たす整数 x, y を計算するアルゴリズムが 拡張ユークリッドの互
除法 である.
問題 3. 1 次方程式 40x + 28y = 4 の整数解 x, y を計算せよ.
整数 a, b に対して, ax + by = GCD(a, b) を満たす整数 x, y を計算する. a, b に対して, ユークリッドの互除法を適用.
r1 = a, r2 = b とおいておく. ri は ri−2 を ri−1 で割った余りとし, qi−1 をその商とおく. rn+1 = GCD(a, b) であるとす
る. 各 ri が ri = (整数) · a + (整数) · b の形で書けることを見ていく.
r1 =a
r1 =1 · a + 0 · b = x1 · a + y1 · b
r2 =b
r2 =0 · a + 1 · b = x2 · a + y2 · b
r1 =q2 r2 + r3
r3 =r1 − q2 · r2 = (x1 − q2 x2 ) · a + (y1 − q2 y2 ) · b = x3 · a + y3 · b
r2 =q2 r3 + r4
r4 =r2 − q3 · r3 = (x2 − q3 x3 ) · a + (y2 − q3 x3 ) · b = x4 · a + y4 · b
···
rn+1 =rn−1 − qn · rn = (xn−1 − qn xn ) · a + (yn−1 − qn yn ) · b
rn−1 =qn rn + rn+1
rn =qn+1 rn+1 + 0
これより,
GCD(a, b) = rn+1 = (xn−1 − qn xn ) · a + (yn−1 − qn yn ) · b
ここで, xi , yi は,
xi = xi−2 − qi−1 xi−1
(i ≥ 2),
x1 = 1,
x2 = 0,
yi = yi−2 − qi−1 yi−1
(i ≥ 2),
y1 = 0,
y2 = 1
で決まる整数である.
アルゴリズム 4 (拡張ユークリッドの互除法).
入力 : 整数 a, b, 出力 : GCD(a, b) と xa + yb = GCD(a, b) を満たす整数 x, y
1. r1 ← a,
x1 ← 1,
y1 ← 0
2. r2 ← b,
x2 ← 0,
y2 ← 1
3. r2 ̸= 0 である限り, 4, 5, 6, 7 を続ける.
1
4.
r3 ← (r1 を r2 で割った余り),
5.
x3 ← x1 − qx2 ,
6.
r1 ← r2 ,
7.
1 へ.
q ← (r1 を r2 で割った商)
y3 = y1 − qy2
r 2 ← r3 ,
x1 ← x2 ,
x2 ← x3 ,
y 1 ← y2 ,
y2 ← y3
8. r1 , x1 , y1 を出力.
プログラム 5 (拡張ユークリッドの互除法のプログラム). 拡張ユークリッドの互除法を Asir で実装する.
ex gcd.rr
def ex_gcd(A, B)
{
R1 = A;
X1 = 1;
X2 = 0;
R2 = B;
X2 = 0;
Y2 = 1;
while (R2 != 0) {
R3 = R1 % R2;
Q = idiv(R1, R2);
X3 = X1 - Q * X2;
Y3 = Y1 - Q * Y2;
R1 = R2;
R2 = R3;
X1 = X2;
X2 = X3;
Y1 = Y2;
Y2 = Y3;
}
return [R1, X1, Y1];
}
end$
問題 6. プログラムを利用して, 43091x + 40531y = 1 を満たす整数 x, y を求めよ.
問題 7. プログラムを利用して, 11111x + 1111111y = GCD(11111, 1111111) を満たす整数 x, y を求めよ.
問題 8. プログラムを利用して, 123456789x + 987654321y = GCD(123456789, 987654321) を満たす整数 x, y を求めよ.
問題 9. 計算の途中経過も表示するように ex gcd を書き換えよ.
2
多項式に対するユークリッドの互除法
1 変数の多項式についても, 整数と同様に割り算を行うことができた. 約元や公約元や最大公約元なども, 整数と同様
に定義することができる.
例 10. 多項式 f = x3 + x2 + x + 2 を多項式 g = x + 1 で割り算した時, 商は x2 + 1, 余りは 1 である. 割られる元と割
る元の関係式は, f = (x2 + 1)g + 1 となる.
例 11. 多項式 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) である.
問題 12. 多項式 f = x4 + x3 + x2 + x + 1 を g = x2 + 2 で割った商と余りを計算せよ.
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
定理 13 (ユークリッドの互除法の原理 (多項式)). 多項式 f, g について, f を g で割った商を q とし, 余りを r とする.
(deg r ≤ deg g) が成り立つ.）この時, GCD(f, g) = GCD(g, r) が成り立つ.
（すなわち, f = qg + r
例 14. GCD(x3 + 9x2 + 26x + 24, x3 + 7x2 + 14x + 8) を計算する.
x3 + 9x2 + 26x + 24 =1 · (x3 + 7x2 + 14x + 8) + (2x2 + 12x + 16)
(
)
1
1
3
2
x + 7x + 14x + 8 =
x+
· (2x2 + 12x + 16) + 0
2
2
だから,
GCD(x3 + 9x2 + 26x + 24, x3 + 7x2 + 14x + 8) = GCD(x3 + 7x2 + 14x + 8, 2x2 + 12x + 16) = 2x2 + 12x + 16
問題 15. GCD(x6 − 1, x4 − 1) を手で計算してみよ.
アルゴリズム 16 (ユークリッドの互除法 (多項式)).
入力 : 多項式 f, g, 出力 : GCD(f, g)
1. g ̸= 0 である限り, 2, 3, 4 を続ける.
2.
r ← (f を g で割った余り)
3.
f ← g,
4.
1 へ.
g←r
5. f を出力.
プログラム 17 (ユークリッドの互除法 (多項式) のプログラム). Asir で上のアルゴリズムを実装すると次のようになる.
p gcd.rr
def p_gcd(F, G)
{
while (G !=
R =
F =
G =
}
return F;
}
end$
0) {
srem(F, G);
G;
R;
問題 18. 上のプログラムを使って, GCD(x6 − 14x4 + 49x2 − 36, x6 − 6x5 + 11x4 − 5x3 − 6x2 + 11x − 6) を計算せよ.
3
© Copyright 2024 ExpyDoc
