ユークリッドの互除法：最大公約数
ユークリッドの互除法はあらゆるアルゴリズムのおじいさんである。今日まで生きのびている、自明でないアルゴリズムのなかで最も古いのだから。
— ドナルド・クヌース『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$ です。
