Euler's Eyes
2026-10-14
ユークリッドの互除法：最大公約数
ユークリッドの互除法はあらゆるアルゴリズムのおじいさんである。今日まで生きのびている、自明でないアルゴリズムのなかで最も古いのだから。
— ドナルド・クヌース『The Art of Computer Programming』第 2 巻（1969）
長さ 252 cm と 105 cm の二本の棒があって、どちらもちょうど整数回で測れるいちばん長い物差しを見つけたいとします。今日のことばでは 最大公約数 $\gcd(252,105)$ が知りたいわけです。それぞれの数の約数をすべて書きだして、共通するいちばん大きなものを探してもよいのですが、大きな数ではそうはいきません。『原論』の第七巻で、ユークリッドはずっと速い方法を教えています。
大きいほうから小さいほうを引く
命題 VII.1 と VII.2 でのユークリッドの考えは単純です。二本の棒を測れる物差しは、その 差 も測れる。だから 252 と 105 の共通の尺度を探すかわりに、105 と $252-105=147$ について探してもよい。それから 105 と $147-105=42$ について。いつも大きいほうから小さいほうを引き、二つが等しくなるまで続けます。
$$(252,105)\to(147,105)\to(42,105)\to(42,63)\to(42,21)\to(21,21).$$どちらも 21 になりました。これが最大公約数です。ギリシャ人はこの手続きを アンテュパイレシス、「たがいに引くこと」と呼びました。
割り算による版
同じ数を何回も引くのは、割ることです。くり返しの引き算を余りのある割り算にまとめると、アルゴリズムは短くなります。
$$\begin{aligned}252&=2\cdot105+42\\105&=2\cdot42+21\\42&=2\cdot21+0\end{aligned}$$最後の 0 でない余りが最大公約数です。
$$\boxed{\gcd(252,105)=21.}$$なぜうまくいくのか
$a=qb+r$ なら、
- $a$ と $b$ をともに割りきる数は、$r=a-qb$ も割りきる。
- $b$ と $r$ をともに割りきる数は、$a=qb+r$ も割りきる。
組 $(a,b)$ と $(b,r)$ の公約数はまったく同じなので、$\gcd(a,b)=\gcd(b,r)$ です。では、なぜアルゴリズムは 終わる のでしょう。余りは一歩ごとに小さくなる正の整数で、$42>21>0$、そして正の整数がいつまでも小さくなりつづけることはできないからです。いつかは余りが 0 になり、$\gcd(d,0)=d$ です。
このアルゴリズムは速いのです。フランスのガブリエル・ラメは 1844 年に、割り算の回数は二つの数のうち小さいほうの桁数の五倍を超えないことを証明しました。百桁の数でも、割り算は多くて 500 回ですみます。
計算を逆にたどる
計算を使えば、最大公約数をもとの二つの数の 組みあわせ で書くこともできます。下から上へたどりましょう。
$$\begin{aligned}21&=105-2\cdot42\\&=105-2\cdot(252-2\cdot105)\\&=5\cdot105-2\cdot252.\end{aligned}$$確かめると $525-504=21$。一般に、どんな $a$ と $b$ についても、$ax+by=\gcd(a,b)$ となる整数 $x$、$y$ があります。これが ベズーの等式 で、逆にたどる手続きは 拡張ユークリッド互除法 と呼ばれます。
練習問題：391 と 299 の最大公約数を求めよ。
$391=1\cdot299+92$、$299=3\cdot92+23$、$92=4\cdot23+0$。最大公約数は 23 です。実際、$391=17\cdot23$、$299=13\cdot23$ です。
練習問題：分数 252/105 を約分し、1 を 12 と 5 の組みあわせで表せ。
分子と分母を最大公約数 21 で割ると、$\frac{252}{105}=\frac{12}5$。次に $12=2\cdot5+2$、$5=2\cdot2+1$。逆にたどると、$1=5-2\cdot2=5-2\cdot(12-2\cdot5)=5\cdot5-2\cdot12$。確かめると $25-24=1$。
出典： 『原論』命題 VII.1 と VII.2、D. E. Joyce 版 · Donald E. Knuth、The Art of Computer Programming、第 2 巻、4.5.2 節 · Gabriel Lamé、“Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur”、Comptes rendus 19（1844）。