ユ ー クリッド の 互除法じょほう と 最大公約数さいだいこうやくすう

この 章しょう で 学まなぶ こと

前章ぜんしょう で 学がく ん だ (\gcd) を、 素因数そいんすう分解ぶんかい し な く て も 求もとめ め る 方法ほう が ユークリッドの互除法ゆーくりっどのごじょほう です。 こ の 強力きょうりょく な 道具どうぐ は、 古代こだい ギ リ シ ャ の ユ ー ク リ ッ ド 「原げん論ろん」 (約やく 2300 年ねん前ぜん) に 既すんで に 記き載さい さ れ て い ま す。

• 整数の割り算定理せいすうのわりざんていり を 確かく認にん す る
• ユークリッドの互除法ゆーくりっどのごじょほう で (\gcd) を 求もとめ め る
• 「割わり り 算さん の 余よ り」 で 次々つぎつぎ と 割わり り 続ぞく け る 仕組く み を 理り解かい す る
• 拡張ユークリッド互除法かくちょうゆーくりっどごじょほう で (ax + by = \gcd(a, b)) の 整せい数すう解かい を 求もとめ め る

ポイント: 互除法じょほう は 「(a) を (b) で 割わり っ た 余よ り を 使し う」 だ け の シ ン プ ル な 操作そうさ。 計算けいさん量りょう が と て も 少しょう な い の で、 大だい き な 数かず に も 効こう き ま す。

1. 整数せいすう の 割わり 算定さんてい理り

定理ていり

整せい数すう (a) と 正ただし の 整せい数すう (b) に 対たい し、

[ a = bq + r \quad (0 \le r < b) ]

を 満みつる た す 整せい数すう (q, r) が た だ 一いち通つう り 存在そんざい し ま す。 (q) を 商しょう、 (r) を 余あまり と 呼こ び ま す。

例れい: (23 = 5 \cdot 4 + 3) (商しょう 4、 余よ り 3)、 (100 = 7 \cdot 14 + 2) (商しょう 14、 余よ り 2)。

重要じゅうよう な 性質せいしつ

[ \gcd(a, b) = \gcd(b, r) \quad (a = bq + r) ]

つ ま り 「(a) と (b) の (\gcd)」 = 「(b) と 余よ り の (\gcd)」。 こ れ が 互除法じょほう の 心しん臓ぞう部 です。

性質せいしつ の 証明しょうめい

(a = bq + r) よ り (r = a - bq)。 (d) が (a, b) の 共きょう通つう約やく数すう な ら (d \mid (a - bq) = r) で あ り、 逆ぎゃく に (d) が (b, r) の 共きょう通つう約やく数すう な ら (d \mid (bq + r) = a)。 し た が っ て 「(a, b) の 共きょう通つう約やく数すう」 と 「(b, r) の 共きょう通つう約やく数すう」 は 完かん全ぜん に 一いっ致ち し ま す。

2. ユ ー クリッド の 互除法じょほう

手順てじゅん

(\gcd(a, b)) を 求もとめ め る ((a > b > 0) と す る) 手順てじゅん:

1. (a) を (b) で 割わり り、 余よ り (r_1) を 求もとめ め る
2. 次つぎ に (b) を (r_1) で 割わり り、 余よ り (r_2) を 求もとめ め る
3. 同様どうよう に 続ぞく け、 余よ り が 0 に な っ た と き の 直前ちょくぜん の 余よ り (= 割わり る 方かた) が (\gcd)

例題れいだい 1: gcd(252, 198)

割わり ら れ る	割わり る	商しょう	余よ り
252	198	1	54
198	54	3	36
54	36	1	18
36	18	2	0

余よ り が 0 に な っ た と き の 割わり る 方かた が 18 な の で、 (\gcd(252, 198) = 18)。

検算けんざん: (252 = 2^2 \cdot 3^2 \cdot 7)、 (198 = 2 \cdot 3^2 \cdot 11)、 共きょう通つう = (2 \cdot 3^2 = 18) ○。

例題れいだい 2: gcd(2730, 663)

割わり ら れ る	割わり る	商しょう	余よ り
2730	663	4	78
663	78	8	39
78	39	2	0

(\gcd = 39)。

例題れいだい 3: gcd(1071, 1029)

(1071 = 1029 \cdot 1 + 42)、 (1029 = 42 \cdot 24 + 21)、 (42 = 21 \cdot 2 + 0)。 (\gcd = 21)。

3. 互除法じょほう の 計算けいさん量りょう

なぜ 速はやい か

各かく ス テ ッ プ で 数かず が お お む ね 半分はんぶん以下いか に な り ま す (フィボナッチ数フィボナッチすう が 最悪さいあく ケ ー ス)。 し た が っ て (\log_2 a) ス テ ッ プ 程度ていど で 終おわり わ り ま す。

(a, b) が 10 億おく程度ていど で も 数すう十じゅう回かい の 割わり り 算さん で (\gcd) が 求もとめ ま る の で、 コ ン ピ ュ ー タ の 暗号あんごう計算けいさん (RSA な ど) で も 中心ちゅうしん的てき に 使し わ れ ま す。

4. 拡張かくちょう ユ ー クリッド 互除法じょほう

目標もくひょう

整せい数すう (a, b) に 対たい し、

[ ax + by = \gcd(a, b) ]

を 満みつる た す 整せい数すう解かい ((x, y)) を 求もとめ め ま す。 (こ の 形かたち は 次じ章しょう の 不定方程式ふていほうていしき の 出発しゅっぱつ点てん)。

解かい が 存在そんざい す る こ と

ベズーの等式ベズーのとうしき: 任にん意い の 整せい数すう (a, b) (両方りょうほう 0 で な い) に 対たい し、 (ax + by = \gcd(a, b)) を 満みつる た す 整せい数すう (x, y) が 必 ず 存在そんざい し ま す。

求もとめ 方かた (逆ぎゃく向むこう き 代入だいにゅう)

互除法じょほう を 行あるき い、 余よ り の 式しき を 上うえ か ら 順じゅん に 並なみ べ、 下か か ら 順じゅん に 代入だいにゅう し て い き ま す。

例題れいだい 4: 252x + 198y = 18 の 整数せいすう解かい

ま ず 互除法じょほう (例題れいだい 1) の 結果けっか を 並なみ べ ま す。

[\begin{aligned} 252 &= 198 \cdot 1 + 54 \ 198 &= 54 \cdot 3 + 36 \ 54 &= 36 \cdot 1 + 18 \ 36 &= 18 \cdot 2 + 0 \end{aligned}]

下した か ら 逆算ぎゃくさん:

[\begin{aligned} 18 &= 54 - 36 \cdot 1 \ &= 54 - (198 - 54 \cdot 3) = 54 \cdot 4 - 198 \ &= (252 - 198) \cdot 4 - 198 = 252 \cdot 4 - 198 \cdot 5 \end{aligned}]

し た が っ て (x = 4, y = -5) が 1 つ の 整せい数すう解かい。 検算けんざん: (252 \cdot 4 - 198 \cdot 5 = 1008 - 990 = 18) ○。

例題れいだい 5: 17x + 12y = 1

(\gcd(17, 12) = 1) な の で 整せい数すう解かい が 存在そんざい。 互除法じょほう:

(17 = 12 \cdot 1 + 5)、 (12 = 5 \cdot 2 + 2)、 (5 = 2 \cdot 2 + 1)、 (2 = 1 \cdot 2 + 0)。

逆算ぎゃくさん:

[\begin{aligned} 1 &= 5 - 2 \cdot 2 \ &= 5 - (12 - 5 \cdot 2) \cdot 2 = 5 \cdot 5 - 12 \cdot 2 \ &= (17 - 12) \cdot 5 - 12 \cdot 2 = 17 \cdot 5 - 12 \cdot 7 \end{aligned}]

し た が っ て (x = 5, y = -7)。 検算けんざん: (17 \cdot 5 - 12 \cdot 7 = 85 - 84 = 1) ○。

5. 章しょう末まつ ま とめ

道どう具ぐ	公こう式しき と 手順てじゅん
割わり り 算定さんてい理り	(a = bq + r)、 (0 \le r < b)
互[除法	じょほう] の [核
[計算	けいさん][法
[計算	けいさん][量
[拡張	かくちょう][版

次じ の 章しょう で は: 一いち次じ不定ふてい方程式ほうていしき (ax + by = c) の 整せい数すう解かい を 互除法じょほう を 用よう い て 求もとめ め、 一いち次じ合同ごうどう式しき の 基き礎そ を 学がく び ま す。