5 ユークリッドの互除法

ユークリッドの互除法11
5
最後に 488 ÷ 61 を計算すると 488 = 61 × 8 だから,
gcd(488, 61) = 61
前回, 公約数および最大公約数について学習した. a と b の共通の約
数のことを公約数, 公約数のうち最大のものを最大公約数と言った. 復
となる. 以上の式 (5.2)–(5.4) の計算から, gcd(2501, 2013) = 61 となる
習のため, 次の問題を考えてみよう.
ことが分かった.
計算間違いがないかチェックするため, 2501 と 2013 が 61 で割れるか
問題 5.1. 次を計算せよ.
(1) gcd(24, 36),
(5.4)
確認する. 筆算計算により,
(2) gcd(42, 102).
2501 = 61 × 41,
前回の問題で次の問題を出題した:
gcd(2501, 2013).
2013 = 61 × 33
となり, 確かに 61 で割り切れることが分かる.12 このような計算方法を
(5.1)
ユークリッドの互除法という.
2501, 2013 の約数を全て計算し, 共通の約数で最大のもの, と考えると
手計算ではかなり大変そうである. このような大きな数どうしの最大公
約数の計算方法で有効なユークリッドの互除法が今日のテーマである.
前回の授業で, 次の定理を証明した:
問題 5.2. 上の計算方法を真似して, 次を計算せよ.
(1) gcd(1829, 1357),
(2) gcd(12345, 67890).
計算が終わったら, 求めた最大公約数が共通の約数になっていることを
確認すること.
定理 5.1 (= 定理 4.7). a と b を 0 でない整数, k を整数とする. このと
式 (5.1) や問 5.2 の場合, 割り算と定理 5.1 を何回か繰り返し用いれ
き, 次が成り立つ:
ば, 式 (5.4) の左辺のように一方の数がもう一方の数で割り切れる状況
ができ, 最大公約数を計算することができた. 二つの整数を勝手に与え
gcd(a, b) = gcd(a + kb, b).
たとき, 同様のことが成り立つのか, ということを考えてみる.
定理 5.1 と割り算の原理を用いて式 (5.1) を計算してみよう. まず,
そのために, まず一般的な状況でユークリッドの互除法を説明する.
2501 ÷ 2013 を計算して, 商は 1, 余りは 488, つまり, 2501 = 2013 × 1 +
488 なので,
a と b を正の整数で b ≤ a とし, gcd(a, b) を次の操作で計算する.
1 回目の操作: a ÷ b を計算し,
gcd(2501, 2013) = gcd(2013 × 1 + 488, 2013) = gcd(488, 2013) (5.2)
a = bq1 + r1 かつ 0 ≤ r1 < b
となる. ここで, 2 番目の = で定理 5.1 を a = 488, b = 2013, k = 1 と
を満たす整数 q1 , r1 を求める. r1 = 0 ならばアルゴリズムを終了する.
して用いた. さらに, 2013 ÷ 488 を計算し, 2013 = 488 × 4 + 61 だから,
gcd(488, 2013) = gcd(488, 488 × 4 + 61) = gcd(488, 61).
11
(5.5)
r1 = 0 ならば次の操作を行う.
12
このように結果に間違いがないか容易に調べることができるので, 計算が終わった
ら検算をする癖をつけよう. 誤った答えが出たとき, それに気づけることも数学の素養
の一つである.
(5.3)
[芹沢, pp.83–90], [シル, 第 5 章]
10
2 回目の操作: b ÷ r1 を計算し,
証明. 背理法で証明する. 上の操作を b 回繰り返してもアルゴリズムが
b = r1 q2 + r2 かつ 0 ≤ r2 < r1
終わらない, つまり, r1 , . . . , rb はすべて 0 でないとする. 式 (5.5),. . ., 式
(5.6)
(5.8) で n = b としたものの不等式の部分を書き並べてみると, 背理法
の仮定 rb = 0 に注意して,
を満たす整数 q2 , r2 を求める. r2 = 0 ならばアルゴリズムを終了する.
r2 = 0 ならば次の操作を行う.
0 < rb < rb−1 < · · · < r3 < r2 < r1 < b
3 回目の操作: r1 ÷ r2 を計算し,
(5.9)
となる. 0 より大きく b 未満の整数は 1, 2, . . . , b − 1 の b − 1 個である.
r1 = r2 q3 + r3 かつ 0 ≤ r3 < r2
一方, r1 , . . . , rb は 0 より大きく b 未満の b 個の相異なる整数である. こ
(5.7)
れは矛盾である. よって, 操作は高々b 回で終了する.
を満たす整数 q3 , r3 を求める. r3 = 0 ならばアルゴリズムを終了する.
よって, 割り算の原理を繰り返すと, 一方がもう一方を割り切る状況
r3 = 0 ならば次の操作を行う.
ができることが分かった. そこで, rl = 0 となったとすると, 定理 5.1 と
式 (5.5)–(5.8)(で n = l としたもの) より,
···
gcd(a, b) = gcd(bq1 + r1 , b) = gcd(r1 , b)
n 回目の操作: ((n − 2) 回目の操作で求めた rn−2 と, (n − 1) 回目の操
作で求めた rn−1 に対し) rn−2 ÷ rn−1 を計算し,
rn−2 = rn−1 qn + rn かつ 0 ≤ rn < rn−1
= gcd(r1 , r1 q2 + r2 ) = gcd(r1 , r2 )
= gcd(r2 q3 + r3 , r2 ) = gcd(r3 , r2 )
(5.8)
= ···
を満たす整数 qn , rn を求める. rn = 0 ならばアルゴリズムを終了する.
= gcd(rl−2 , rl−1 )
rn = 0 ならば次の操作を行う.
= gcd(rl−1 ql , rl−1 ) = rl−1
···
となる. 最後の行の一つ目の等式で rl = 0, つまり rl−2 = rl−1 ql + rl =
rl−1 ql を用いた. この結果より, 割り算の原理を繰り返し用いたとき, 余
りが 0 となるものの一つ前の割り算の余りが最大公約数となることが
分かった.
まず, 上の操作について次のことを証明する.
補題 5.2. b ≤ a を満たす正の整数 a, b に対し, 上の操作を考える. こ
のとき, 高々b 回で上の操作は終了する. つまり, rl = 0 かつ l ≤ b を満
問題 5.3. ユークリッドの互除法を用いて次を計算せよ. 答えが出たら
たす正の整数 l が存在する.13
検算もすること.
13
「高々b 回」は非常に多いと感じるかもしれない. 例えば, b = 2013 の場合, 運が悪
いと 2013 回も割り算しなくてはいけないのだろうか. 実は, 上記操作は (b の桁数)×5
回以下で終了することが知られている (ラメの定理). b が 4 桁の数なら最悪 20 回割り
算すれば, アルゴリズムは終了するのである.
gcd(23533, 49163).
11

Download Report