ユークリッドの互除法はなぜ「最大」公約数を見つけるのか ― 引き算から割り算へ
gcd(a,b)=gcd(b, a mod b) という再帰の背後にある不変量を明らかにし，引き算による素朴な方法から割り算への改良，ベズーの等式，拡張ユークリッドによる逆元計算までを解説します．
ユークリッドの互除法は，紀元前300年頃に記された『原論』に登場する，人類最古のアルゴリズムのひとつです．しかし教科書では「」と書いて終わりがちです．なぜこの操作で最大公約数が求まるのでしょうか？
1 最大公約数の定義
定義 1 (最大公約数).
整数 （ともに でない）の最大公約数 とは， と の両方を割り切る正の整数のうち最大のものです．
注意 2.
は「 と に共通する因数をすべて集めたもの」と直感的に理解できます．たとえば です（， なので，共通部分は ）．
2 引き算による素朴な方法
最大公約数を求める最も素朴な方法は，引き算の繰り返しです．
定理 3 (引き算の不変量).
のとき，．
証明.
かつ ならば ．逆に かつ ならば ．よって の公約数の集合と の公約数の集合は一致し，その最大値も一致します． □
例 4.
を引き算で求めます：
この方法は正しいですが，との差が大きいと非常に遅くなります（は回の引き算が必要）．
3 割り算への改良 ― なぜ高速化するか
引き算を繰り返す代わりに，一気に割り算してしまいましょう．
定理 5 (ユークリッドの互除法の核心).
のとき，．
証明.
（）とします． かつ ならば ．逆に かつ ならば ．よって ． □
注意 6.
引き算版では と 1 ステップで が だけ減ります．割り算版では と 1 ステップで を で割った余りまで一気に小さくなります．引き算を 回まとめて行ったのと同じです．
定理 7 (計算量).
ユークリッドの互除法の計算量は です．
注意 8.
なぜ対数オーダーになるのでしょうか？ 鍵は「」が常に成り立つことです． なら余りは 未満なので 未満． なら ．つまり 2 ステップごとに値が半分以下になり， ステップで終了します．
4 ベズーの等式 ― GCD は線形結合で書ける
定理 9 (ベズーの等式).
整数 に対し，
をみたす整数 が存在します．
証明.
ユークリッドの互除法を逆にたどることで構成的に を求められます．基底ケース ．再帰ステップ： と書けているとき， を代入すると ． □
5 拡張ユークリッドの互除法
ベズーの等式の証明をアルゴリズムにしたのが拡張ユークリッドの互除法です．
例 10.
を求め， の解を構成します：
6 逆元計算への応用
定理 11 (mod での逆元).
のとき， をみたす が存在します．この を の を法とする逆元と呼びます．
証明.
ベズーの等式より となる が存在します．両辺を で見ると です． □
注意 12 (競プロでの逆元計算).
が素数のとき，（）なので，拡張ユークリッドで逆元を で求められます．フェルマーの小定理を使う よりも定数倍が軽く， が素数でない場合にも使えるのが利点です．
7 まとめ
GCD の計算は「公約数の集合が不変」という不変量に基づいています
引き算 → 割り算の改良で の高速アルゴリズムになります
ベズーの等式は GCD が線形結合で表せることを保証します
拡張ユークリッドにより，mod 逆元が効率的に計算できます
次の記事では，整数の「原子」である素数と，算術の基本定理がなぜ成り立つのか（そしてどこで崩壊するのか）を見ていきます．