ユークリッドの互除法とは？ 10分でわかりやすく解説

最大公約数（GCD）を求める方法はいくつかありますが、実務で使われる代表格が「ユークリッドの互除法」です。計算が速く、暗号やアルゴリズムの基礎としても頻繁に登場します。この記事では、互除法の考え方・手順・正しさの理由から、実装の注意点や応用（拡張互除法）までを一通り整理し、読了後に「どの場面でどう使うべきか」を判断できるようにします。

ユークリッドの互除法とは

ユークリッドの互除法とは、2つの整数の最大公約数（GCD）を効率よく求めるアルゴリズムです。古代ギリシャの数学者ユークリッドが著書『原論』で紹介したことで知られ、現代でも整数論・コンピュータサイエンス・暗号理論など幅広い分野で利用されています。

ユークリッドの互除法の定義

ユークリッドの互除法は、次の手順で定義できます。

1. 2つの整数 a と b（a ≧ b、b ≠ 0）が与えられたとき、a を b で割った余りを r とする（a = bq + r）。
2. もし r が 0 ならば、b が最大公約数（GCD）である。
3. そうでなければ、(a, b) を (b, r) に置き換え、同じ手順を繰り返す。

この繰り返しは必ず終了し、最終的に得られた「余りが 0 になった直前の除数」が最大公約数になります。

最大公約数（GCD）について

最大公約数（GCD）とは、2つ以上の整数の共通の約数のうち最大のものを指します。例えば、24 と 36 の共通の約数は 1, 2, 3, 4, 6, 12 で、この中で最大は 12 なので gcd(24, 36) = 12 です。

GCD は、分数の約分（例：36/24 を 3/2 にする）、比の簡約、周期・パターンの揃え（同じ区切りで割れるか）など、実務でも地味に登場します。また、暗号や数論の基礎でも重要です。

ユークリッドの互除法の歴史

ユークリッドの互除法は、紀元前3世紀ごろのユークリッドが『原論』で紹介した方法として広く知られています。現代的には「最大公約数を求める標準的な手法」であり、実装も容易で計算量も小さいため、各種プログラミング言語やライブラリで広く採用されています。

ユークリッドの互除法が重要な理由

• 効率性：除算と剰余の繰り返しで計算でき、大きな整数でも比較的速く求まります。
• 汎用性：GCD 計算だけでなく、拡張版により「一次不定方程式」や「モジュラ逆元」にも応用できます。
• 理解しやすさ：アルゴリズムが短く、数学的な裏付けも比較的シンプルです。

ユークリッドの互除法のアルゴリズム

ここでは、互除法の核となる性質、具体例、正しさの理由（証明の骨子）、計算量の見方を整理します。

ユークリッドの互除法の基本的な考え方

ユークリッドの互除法の本質は、次の等式にあります。

gcd(a, b) = gcd(b, a mod b)

つまり、(a, b) の最大公約数は、(b, 余り r) の最大公約数と同じです。この等式を繰り返し適用すれば、余りが 0 になるまで計算を縮められ、最後に残った除数が GCD になります。

なお、「差を取っていく（gcd(a, b) = gcd(a-b, b) のような性質）」も同じ発想の一部ですが、実装としては除算（剰余）を使う互除法の方が圧倒的に少ない回数で済むため、一般にこちらが使われます。

具体例（24 と 36）

1. 36 ÷ 24 = 1 余り 12
2. 24 ÷ 12 = 2 余り 0

余りが 0 になったので、直前の除数 12 が最大公約数です。

Pythonでの基本実装例

反復（ループ）で書くと簡潔です。

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

負の数が入っても GCD は通常「非負」で扱うため、abs() を先に適用しています。

ユークリッドの互除法の証明（骨子）

a = bq + r（q は商、r は余り）とします。d を a と b の共通の約数とすると、d は a と b を割り切るので、r = a - bq も割り切ります。よって d は b と r の共通の約数でもあります。

逆に、d を b と r の共通の約数とすると、a = bq + r も割り切れるため、d は a と b の共通の約数でもあります。

したがって a と b の共通の約数集合と、b と r の共通の約数集合は一致し、gcd(a, b) = gcd(b, r)が成り立ちます。この等式を繰り返すのが互除法です。

ユークリッドの互除法の計算量

互除法は、入力サイズ（概ね桁数）に対して効率が良いことで知られています。一般に、計算量は O(log(min(a, b))) 程度（より正確には除算回数は対数オーダー）と見積もれます。最悪ケースは連続するフィボナッチ数に近い組み合わせで回数が増えることが知られていますが、それでも増え方は緩やかです。

「素因数分解して GCD を求める」方法は、巨大整数では現実的でないことが多いため、実装や実務では互除法が第一選択になります。

ユークリッドの互除法の応用

互除法は GCD を求めるだけでなく、数論・暗号・アルゴリズムの土台としても使われます。ここでは代表的な2つを紹介します。

ユークリッドの互除法と連分数

ユークリッドの互除法の各ステップで得られる「商」は、有理数を連分数展開するときの要素になります。つまり、互除法を辿ることで有理数を連分数として表せるという関係があります。連分数は近似（分数近似）などに利用されます。

ユークリッドの互除法とベズーの等式（拡張互除法）

ベズーの等式は、0 でない整数 a, b に対して gcd(a, b) が

ax + by = gcd(a, b)

の形で表せる（x, y は整数）という性質です。互除法を拡張した拡張ユークリッドの互除法を使うと、この x と y を効率よく求められます。

この仕組みは、RSA などの公開鍵暗号で使う「モジュラ逆元（mod の逆数）」の計算にも直結します。例えば、gcd(a, m) = 1 なら、ax ≡ 1（mod m）を満たす x（逆元）が存在し、拡張互除法で求められます。

ユークリッドの互除法の実装

ここでは、再帰・反復・拡張版の例と、実装時に迷いやすい注意点をまとめます。

再帰的な実装

def gcd_recursive(a, b):
    a, b = abs(a), abs(b)
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

再帰は読みやすい一方、言語や設定によっては再帰の深さ制限があるため、実務では反復（ループ）版が好まれることもあります。

反復的な実装

def gcd_iterative(a, b):
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b
    return a

処理の流れがそのまま書けて、再帰制限の心配も少ない実装です。

拡張ユークリッドの互除法

def extended_gcd(a, b):
    # returns (g, x, y) such that ax + by = g = gcd(a, b)
    if b == 0:
        return abs(a), 1 if a >= 0 else -1, 0
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return g, x, y

返り値の (g, x, y) は、g = gcd(a, b) および ax + by = g を満たします。g が 1 のとき、x は a の mod b における逆元計算などに利用できます（ただし「どの法（mod）での逆元か」により取り扱いは変わるため、用途に応じて整理が必要です）。

実装上の注意点

• ゼロ入力：gcd(a, 0) は一般に |a| です。gcd(0, 0) は数学的に一意に定まりませんが、実装では 0 を返すなど、仕様を決めて扱うことがあります。
• 負の整数：GCD は通常「非負」で定義されるため、abs() を用いて扱うと混乱が減ります。剰余の符号は言語仕様で異なるため、言語に依存しない書き方にするのが安全です。
• 巨大整数：Python の int のように任意精度整数を扱える言語ではオーバーフローは起きにくいですが、固定長整数の言語ではオーバーフローを考慮する必要があります。
• 標準ライブラリ：用途が「GCD を得るだけ」なら、Python では math.gcd の利用が簡単で安全です（実装の学習目的なら自前実装が有効です）。

まとめ

ユークリッドの互除法は、2つの整数の最大公約数（GCD）を求めるための、シンプルで強力なアルゴリズムです。gcd(a, b) = gcd(b, a mod b) の性質を繰り返し使うことで、少ない計算で GCD を求められます。さらに拡張互除法により、ベズーの等式の係数やモジュラ逆元計算にも応用でき、暗号理論やアルゴリズムの基礎として重要な位置を占めています。