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

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

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

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

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

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

定理ていり

整せい数すう $a$ と正せいの整せい数すう $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)(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) の結果けっかを並ならべます。

下から逆算ぎゃくさん:

したがって $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$。

逆算ぎゃくさん:

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

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

道どう具ぐ	公こう式しき と手順てじゅん
割わり算ざん定理ていり	$a=bq+r$、
互除法じょほうの核かく	$\gcd (a,b)=\gcd (b,r)$
計算けいさん法ほう	余あまりが 0 になるまで割わり続つづける
計算けいさん量りょう	$O(\log \min (a,b\left)\right)$
拡張かくちょう版ばん	$ax+by=\gcd (a,b)$ の整せい数すう解かいを逆算ぎゃくさんで求もとめる

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