プログラミングの背景：数論
ユークリッドの互除法
tbasic.org
*1
[2014 年 6 月版]
ユークリッドの互除法は今日まで生き残ってい
る意味のあるアルゴリズムのうち最古のもので，
あらゆるアルゴリズムの祖父と呼ぶことができる。
（ドナルド・クヌース
「The Art of Computer Programming 」)
ユークリッドの互除法は最大公約数を計算する効率的な方法です。この方法の起源は古く，しかも，現在で
も重要なアルゴリズムとして使われています。クヌースが述べているように，アルゴリズムの祖父とも譬えら
れています。
ここではこれについて説明します。
目次
1
ユークリッドの互除法の由来
2
2
ユークリッドの互除法とは
2
3
ユークリッドの互除法の原理
3
4
ユークリッドの互除法
4
5
ユークリッド互除法の回数とフィボナッチ数
6
6
ラメの定理
7
*1
http://www.tbasic.org
1
ユークリッドの互除法とは
2
1 ユークリッドの互除法の由来
ユークリッド（-330？∼-275）はユークリッド幾何学の名前で有名な古代ギリシアの数学者です。ユーク
リッドは非常に有名ですが，ユークリッド自身についてはあまり知られていません。確実なことは彼が「原
論」と言われる著作を 残したことぐらいです。*2
「原論」はいわゆるユークリッド幾何学の原典です。このユークリッド「原論」は全 13 巻からなる大著で，
その全貌を見るのは大変ですが，幸い日本語訳が出ていて，身近に触れることも出来ます。比較的大きな図書
館には蔵書されていると思いますから，興味のある人は一度ご覧になってみると良いと思います。
この「原論」は幾何学だけでなく数論も含んだ，当時のギリシア正統的数学の集大成ともいえるものです。
ユークリッドの互除法は「原論」第 7 巻命題 1 から命題 3 に書かれている方法のことです。ユークリッドの互
除法という名前もこのことに由来します。数学史の研究によると，「原論」はユークリッド自身の著作と言う
よりは，当時の数学をまとめた著作と言われています。そしてこの成果はもう少し前のピタゴラスの時代のも
のと言われています。ですから本当はピタゴラスの互除法というのが正しいかもしれません。もっとも，古代
中国や古代インドでも似たようなアルゴリズムがありますので，何処が本当の起源かは不明です。
2 ユークリッドの互除法とは
ユークリッドの互除法は２つの自然数 a, b の最大公約数を計算する方法です。
2 つの数の最大公約数は，それらを測るときの最大の共通尺度で，数を扱うときの基本的な量と言えます。
そのことから，最大公約数を求めることは，数を扱う学問の中では最も基本的な問題として扱われてきました。
a と b の最大公約数を求めるためによく行われる方法として，a と b を素因数分解してその共通項を見つ
けるというものがあります。この方法は小さい数の場合は計算に適していますが，a と b が少し大きくなると
この方法での計算は難しくなります。
例えば，15 と 21 の最大公約数を求めてみます。15 と 21 の素因数分解は，それぞれ
15 = 3 · 5 かつ 21 = 3 · 7
なので，15 と 21 の最大公約数は それらの共通項 3 となります。
しかし，62873258567731 と 62908468304971 の最大公約数をこの方法で簡単に計算できるでしょうか。
勿論頑張って，62873258567731 と 62908468304971 の素因数分解を見つけるという道もあります。しかし，
実は
*2
大きな数の素因数分解は難しいことがある
ユークリッドの「原論」は昔「幾何学原論」といわれたこともありました。しかし，この本は幾何学に限らず多くの内容を含みま
すので，現在では元々の名称「原論」と言われています。
ユークリッドの互除法
3
のです*3 。この難しいという意味は，スーパーコンピューターを使っても現実的にはほぼできないものがある
ということです。この「大きな数が素因数分解が難しいことがある」と言う事実は有名なことで，暗号系の中
にはこの事実を使って安全性を保証しているものもあります。
一般に素因数分解は難しいのですが，実は最大公約数の計算にはそれに比べてはるかに簡単で，効率的な良
い方法があるのです。それがユークリッドの互除法です。例えば 1000 桁の 2 個の数が与えられたとき，それ
らの最大公約数もユークリッドの互除法を使えばパソコン上でもすぐに計算できます*4 。
3 ユークリッドの互除法の原理
整数 a, b ∈ Z の最大公約数を gcd(a, b) と表すことにします。ここで，a, b のうち少なくとも一方は 0 では
ないとします。ユークリッドの互除法は次の性質に基づいています。
ユークリッドの互除法の基本原理
a > b ∈ N とし，a を b で割った時の商を q ∈ N，余りを r とする。（r = 0 または，r ∈ N）, 即ち
a = q · b + r, 0 ≦ r < b
と表されたとする。このとき，gcd(a, b) = gcd(b, r) となる。
証明. 少しだけ抽象的な証明をしてみましょう。
C1 を a と b の公約数全体の成す集合とします。つまり，
C1 = {x ∈ Z | x は a の約数かつ b の約数 }
とします。同様に，C2 を b と r の公約数全体の成す集合とします。つまり，
C2 = {x ∈ Z | x は b の約数かつ r の約数 }
とします。ここで証明することは，C1 = C2 です。
(i) x ∈ C1 とします。このとき， x は a の約数かつ b の約数です。（記号で書くと， x | a かつ x | b です。）
ここで，r = a − q · b に注意すると，整除性の基本性質より， x は r の約数となります。（記号で書くと， x | r
です。）従って，このとき， x は b の約数かつ r の約数です。故に， x ∈ C2 となります。つまり，C1 ⊂ C2 が
示されました。
(ii) 逆に x ∈ C2 とします。このとき， x は b の約数かつ r の約数です。（記号で書くと， x | b かつ x | r で
す。
）ここで，a = q · b + r に注意すると，命題 1.1(1) より， x は a の約数となります。（記号で書くと， x | a
です。
）従って，このとき， x は a の約数かつ b の約数です。故に， x ∈ C1 となります。つまり，C2 ⊂ C1 が
示されました。
*3
□
ここで大きな数とは数百桁以上の数を意味して，この例にあるような 62873258567731 のような数のことではありません。実際，
この数程度なら筆算では難しいでしょうが，適当なソフトウエアを使えば，パソコン上ですぐに素因数分解が可能です。
*4 勿論，1000 桁の数の計算には，対応した適切なソフトウエアが必要ですが，そのようなものは比較的簡単に利用できます。
ユークリッドの互除法
4
4 ユークリッドの互除法
上に述べた基本原理の内容を説明しましょう。これは a = q · b + r としたとき， gcd(a, b) は gcd(b, r)
に等しいと言っています。ですから，gcd(a, b) を求めるには， gcd(b, r) を求めれば良いわけです。ここで
a > b > r の関係があることに注意しましょう。a, b に比べて b, r の方が小さいので計算が簡単なはずです。
もし gcd(b, r) が分からなかったら，今度は b を r で割って同様なことを行えばもっと簡単になります。上の
操作は割り算が出来る間続けられますから，
gcd(x, 0), x > 0
の形になるまで，続けられます。明らかにこの場合 gcd(x, 0) = x ですから，これで求められました。
具体例で確かめましょう。
例 4.1 (62979284285501 と 62873258567731 の最大公約数). a = 62979284285501, b = 62873258567731 から始めて，順次，除法の定理を適用すると次が得られます。
62979284285501 =
62873258567731 =
106025717770
=
1 × 62873258567731 + 106025717770
593 × 106025717770 + 7930121
13370 × 7930121 + 0
(1)
(2)
(3)
上のことから，それぞれ
gcd(62979284285501, 62873258567731) =
gcd(62873258567731, 106025717770)
=
gcd(106025717770, 7930121)
=
gcd(62873258567731, 106025717770)
gcd(106025717770, 7930121)
gcd(7930121, 0) = 7930121
(1)
(2)
(3)
が得られます。従って，
gcd(62979284285501, 62873258567731) ＝ 7930121
となります。このようにユークリッドの互除法を使うと驚くほど簡単に最大公約数が得られました*5 。
このように，62979284285501 と 62873258567731 の最大公約数を，因数分解を使わないで，互除法の原理
を 3 回使うだけで，簡単に求めることが出来ました。
この方法を一般的に表すと次のようになります。
*5
因数分解が難しい場合でも，このように最大公約数が簡単に求められました。今の場合，この結果を使って，因数分解を思いつく
人もいるでしょう。実際，公約数はそれぞれの数の因数になりますから，公約数でそれぞれを割って，
62979284285501 = 7930121 · 7941781, 62873258567731 = 7930121 · 7928411
が得られます。実は今の場合，素因数分解になっています。この素因数分解を，結果を知らずに筆算あるいは電卓を用いて得るの
は，かなり困難なことと予想されるでしょう。
ユークリッドの互除法
5
ユークリッドの互除法
自然数 a, b (a > b) に対して，a を b で割った時の余りを r とする。以下同様な操作を行い，n 回の除法
の定理を適用して，次のようになったとする。a = r0 , b = r1 , r = r2 として表す。
r0
r1
r2
ri−2
rn−2
rn−1
=
=
=
···
=
···
=
=
q1
q2
q3
· r1
· r2
· r3
+
+
+
r2
r3
r4
(0 < r2 < r1 ）
(0 < r3 < r2 ）
(0 < r4 < r3 ）
qi−1
· ri−1
+
ri
(0 < ri < ri−1 ）
qn−1
qn
· rn−1
· rn
+
rn
(0 < rn < rn−1 ）
このとき，
gcd(a, b) = gcd(b, r) = gcd(r0 , r1 ) = · · · = gcd(rn−1 , rn ) = rn
となる。即ち，rn が a と b の最大公約数になる。
上のような操作を行ったとき，何回目かで，必ず，rn−1 = qn · rn の形になることに注意してください。実際，
ri−2 が ri−1 で割り切れなければ，ri > 0 が得られ，
a > b = r1 > r2 > · · · > ri−2 > ri−1 > ri > 0
となります。これらはすべて自然数ですから，このような条件を満たす ri は b 個以上存在しません。従って，
多くとも b 回以下でこれらの操作は終了することになります。
gcd(62979284285501, 62873258567731) の例では，n = 3 回で終了しました。この回数は，この場合の
b = 62873258567731 に比べて極めて少ないものとなっています。ユークリッド互除法が効率的であるといわ
れる理由は，この回数が b に比べて極めて少なくなることが一般に成立することによります。
今の場合は，回数が特に少なくなる例ですが，実はどのような場合でもあまり回数は多くなりません。
この回数の評価についてはラメの定理と言われる定理が有名です。以下ではこの定理を説明します。
ユークリッド互除法の回数とフィボナッチ数
6
5 ユークリッド互除法の回数とフィボナッチ数
ユークリッドの互除法での除法の定理を使う回数が多くなるのはどのような場合かを調べてみると，フィボ
ナッチ数に出会います。フィボナッチ数は，色々なところで出会う不思議な数ですが，次で定義される数列
です。
フィボナッチ数
f0 = 0, f1 = 1 とし，i ≧ 2 に対して，
fi = fi−2 + fi−1
6
で定義される数列をフィボナッチ数列と言う。 fi を i 番目のフィボナッチ数と言う。*
フィボナッチ数の最初の方を計算してみると，
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, · · ·
となります。最初の方はそれ程ではありませんが，次第に急激に大きくなります。例えば，
f10 = 55, f20 = 6765, f30 = 832040, f40 = 102334155, f50 = 12586269025
となります。
ユークリッド互除法とフィボナッチ数の関係を説明しましょう。ユークリッド互除法の過程
ri−2 = qi−1 · ri−1 + ri
を見ると，番号付けは逆ですが，フィボナッチの数列と似た式になっていいることに気が付きます。ここで，
qi ≧ 1 ですから，
ri−2 = qi−1 · ri−1 + ri ≧ ri−1 + ri
が成立します。この右辺はフィボナッチ数の形です。このことに注意すると次の命題が成立することが分かり
ます。
命題 5.1. 仮定と記号を前節ユークリッド互除法の通りとする。即ち，a, b (a > b) に対して，ユークリッドの
互除法を適用して
rn−1 = qn · rn
となり，最大公約数 rn が得られたとする。このとき，n 番目のフィボナッチ数 fn に対して，
b ≧ fn+1
が成立する。
*6
文献によっては，フィボナッチ数を，F0 = 1, F1 = 1, . . . と定義することもあります。ここでの定義と，番号付けがずれるだけで
すが，この場合，色々な結果もそれに応じて修正する必要があります。このように，フィボナッチの数の性質を使う場合は，その
定義を確認する必要があります。
ラメの定理
証明. まず，rn−1 > rn > 0 より，
≧
≧
rn
rn−1
7
f2 = 1
f3 = 2
が分かります。更に，
rn−2
rn−3
rn−4
=
=
=
qn−1 · rn−1 + rn
qn−2 · rn−2 + rn−1
qn−3 · rn−3 + rn−2
≧
≧
≧
...
rn−1 + rn
rn−2 + rn−1
rn−3 + rn−2
≧
≧
≧
f3 + f2
f4 + f3
f5 + f4
=
=
=
f4
f5
f6
となりますから，一般に，0 ≦ i ≦ n に対して，
rn−i
=
qn−i+1 · rn−i+1 + rn−i+2
≧
rn−i+1 + rn−i+2
≧
fi+1 + fi
=
fi+2
が成立します。特に，i = n − 1 のとき，
b = r1
=
q2 · r2 + r3
≧
r2 + r3
≧
fn + fn−1
=
fn+1
□
が得られます。
この命題を使って，ユークリッドの互除法の回数 n の評価ができます。
例 5.1 (b = 12345 の場合). b = 12345 とします。n をユークリッド互除法での除法の定理の適用回数とします。 fi を具体的に計算して
みると， f21 = 10946, f22 = 17711 が得られます。上の命題によれば，
b = 12345 ≧ fn+1
ですから，n ≧ 21 ではありません。即ち，a > b に対して，gcd(a, b) はユークリッドの互除法により高々 20
回の除法の定理の適用で計算可能であることが分かります。
一般的な評価を得るために，フィボナッチ数の具体的な大きさについての評価が必要になります。
6 ラメの定理
フィボナッチ数の一般項は，ビネの公式によって具体的な形が与えられていますが，その形からは大きさの
評価は余り明確ではありません。
ここでは，ビネの公式を使わないで，より直接的な次の評価式を使います。
命題 6.1. n > 2 に対して，α =
√
1+ 5
とすると，
2
fn > αn−2
(∗)
が成立する。
証明. 数学的帰納法で証明しましょう。
(1) 命題の主張は n > 2 の場合ですが，n = 2 のときも似た性質，この場合は等号が成立します。即ち，
f2 = 1, α2−2 = α0 = 1
より， f2 = α0 となります。
ラメの定理
8
(2) n = 3 のときは， f3 と α の値を具体的に比較します。即ち，
f3 = 2, α3−2 = α1 =
√
1+ 5
= 1.61 . . .
2
より， f3 > α1 が成立します。
(3) そこで次に，n ≧ 3 として，n 以下について主張が成立すると仮定します*7 。このとき，α2 = α + 1 に
注意すると，
fn+1 = fn + fn−1 > αn−2 + αn−3 = αn−3 (α + 1) = αn−3 · α2 = αn−1 = α(n+1)−2
となります。これで，(∗) が n + 1 のとき成立することが示されました。
□
これらの命題から，ラメの定理が示されます。
ラメの定理
仮定と記号を前節ユークリッド互除法の通りとする。即ち，a, b (a > b) に対して，ユークリッドの互
除法を適用して
rn−1 = qn · rn
となり，最大公約数 rn が得られたとする。b を 10 進法で表示したときの桁数を m とする。このとき，
5m ≧ n
である。
証明. まず，命題 5.1 と命題 6.1 より，
b ≧ fn+1 > αn−1
が得られます。ここで，log10 α = 0.208 . . . > 0.2 =
1
5
に注意すると，
log10 b > (n − 1) log10 α >
n−1
5
となります。m の定義から
10m > b ≧ 10m−1 故に， m > log10 b ≧ m − 1
ですから，
m>
n−1
即ち， 5m > n − 1
5
となります。ここで，m, n は自然数ですから
5m ≧ n
が得られます。
*7
数学的帰納法 2 の形のものです。
□
ラメの定理
9
命題 5.1 の証明を見てみると，互除法での除法の定理の適用回数が多くなるのは，2 数にフィボナッチ数と
同様な関係があるときであることに気が付きます。そのことに注意して，フィボナッチ数列を見てみると次の
例が見つかります。
例 6.1 (n = 5m となる例). a = 1597 = f17 , b = 987 = f16 として，ユークリッドの互除法を適用してみると，m = 3 で，
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
+
+
+
+
+
+
+
+
+
+
+
+
+
+
610
377
233
144
89
55
34
21
13
8
5
3
2
1
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
より，n = 15 = 5m になる。
上の例は，除法の定理の適用回数が多い例でしたが，そこでは，b は比較的小さい数でした。ラメの定理は
b がどんなに大きな数でも成立します。
例えば a > b で，b が 100 桁の数でも最大公約数 gcd(a, b) は高々 500 回の計算で求まるということです。
100 桁の数は例えば
100000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
です！
© Copyright 2024 ExpyDoc
