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

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

前章ぜんしょうで学まなんだ $\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$ の整せい数すう解かいを互除法じょほうを用もちいて求もとめ、 一次合同式いちじごうどうしきの基き礎そを学まなびます。