ユークリッドの互除法（GCD）
ユークリッドの互除法（GCD）
このレッスンで分かること
- 4 ステップで
6という答えに到達します最大公約数(GCD, Greatest Common Divisor) は、2 つ以上の整数に共通する最大の約数のことです- ユークリッドの互除法は、次の漸化式で表されます
ユークリッドの互除法 とは
最大公約数を
gcd(a, b) = gcd(b, a % b)の漸化式で求める。古典中の古典の再帰アルゴリズム。
最大公約数 (GCD, Greatest Common Divisor) は、2 つ以上の整数に共通する 最大の約数 のことです。gcd(12, 18) = 6、gcd(7, 13) = 1、gcd(100, 25) = 25 という具合。これを求める最古のアルゴリズムが ユークリッドの互除法 で、紀元前 300 年頃の数学者 ユークリッド が著書『原論』で記述したものです。
2300 年以上前から使われているアルゴリズムが、現代でも
O(log min(a, b))という最高クラスの計算量で動く。これがアルゴリズムの美しさだ。
互除法の漸化式
ユークリッドの互除法は、次の漸化式で表されます。
gcd(a, 0) = a(b が 0 になったら a が答え)gcd(a, b) = gcd(b, a mod b)(b > 0 のとき)
この 2 行で完成、というシンプルさが特徴です。a mod b は a を b で割った余り、Python では a % b です。
なぜこれで GCD が求まる？
直感的な説明として、a と b の共通の約数は、b と a mod b の共通の約数とも一致します。たとえば gcd(48, 18) を計算してみます。
プレーンテキスト
gcd(48, 18) = gcd(18, 48 mod 18) = gcd(18, 12)
gcd(18, 12) = gcd(12, 18 mod 12) = gcd(12, 6)
gcd(12, 6) = gcd(6, 12 mod 6) = gcd(6, 0)
gcd(6, 0) = 64 ステップで 6 という答えに到達します。素朴に「1 から順に割ってみる」方法だと最大 min(a, b) 回かかるところ、互除法では O(log min(a, b)) で済むのが強みです。
Mermaid で見る再帰の流れ
図のポイント (テキスト併記)
b = 0まで降りたらaを返し、そのまま6が戻ってきます
b = 0 まで降りたら a を返し、そのまま 6 が戻ってきます。階乗やフィボナッチと違い、掛け算や加算 が起きないので、戻り値はずっと同じです。
Python の実装
Python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)if b == 0: return a が 基底ケース、gcd(b, a % b) が 再帰ケース。たった 3 行のコードで 最大公約数 が求まる、というのがユークリッドの互除法の魅力です。
JavaScript / Java での書き方
JavaScript
function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}Java
public class Solution {
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
}どの言語でも、% (剰余演算子) と if return の組み合わせで書けます。Python に至っては標準ライブラリ math.gcd(a, b) で同じ結果が返るので、本番では組み込み関数を使うのが普通です。
計算量
ユークリッドの互除法の計算量は O(log min(a, b)) です。a と b がフィボナッチ数列の連続する 2 項のとき、最悪計算量になることが知られています (これも面白い性質)。
O(log n)で動くアルゴリズムは、n = 10^18でも 60 回程度の計算で終わる。圧倒的に速い。
よくある間違い
if a == 0: return bを基底にしてしまう。これは別の書き方として正しくは動くが、本レッスンではb == 0: return aで統一する。gcd(a, b)でa < bのときどうなる？ → 心配無用。a % bがaのままになるので、次のステップでgcd(b, a)と引数が入れ替わり、b > aの状態に補正される。- 負の数を渡された場合の挙動を考えていない。本レッスンでは
a, b >= 1を前提とする。
やってみよう
下の coding 課題で、gcd(a, b) をユークリッドの互除法で実装してください。テストでは gcd(12, 18) = 6 のような典型ケースに加え、gcd(7, 13) = 1 (互いに素) や gcd(100, 25) = 25 のような片方が倍数のケースもチェックします。for / while / 組み込み math.gcd は使わず、必ず再帰で書いてください。
ユークリッド互除法は
RSA 暗号モジュラ逆元の計算など、暗号理論の基礎としても使われている。2300 年経っても現役、というのは驚異的だ。
最小公倍数 (LCM) との関係
最大公約数 (GCD) と 最小公倍数 (LCM) には、次の有名な関係があります。
lcm(a, b) = a * b / gcd(a, b)
この式を使えば、gcd を実装するだけで lcm も自動的に計算できる、ということです。たとえば lcm(12, 18) = 12 * 18 / 6 = 36 です。gcd がいかに基礎的なアルゴリズムか、よく分かる例です。
Python
def lcm(a, b):
return a * b // gcd(a, b)3 つ以上の GCD
gcd(a, b, c) のように 3 つ以上の数の最大公約数を求めたい場合は、gcd(gcd(a, b), c) のように 2 つずつまとめて計算すれば OK です。これは gcd が 結合則 を満たすことから保証されます。reduce 関数と組み合わせると、配列全体の gcd も 1 行で書けます。
Python
from functools import reduce
def gcdAll(arr):
return reduce(gcd, arr)本レッスンの coding 課題では 2 引数版の gcd のみを扱いますが、関数を 1 つ実装するだけで、lcm や 配列の gcd まで広がる、というのが アルゴリズムの応用力 の面白さです。
よくある質問
Q. このトピックは実務でどう役立ちますか？
A. DB のクエリ最適化、API 設計、データ構造の選択など、設計判断の根拠になります。表面的にライブラリを使うだけでなく「なぜそれが速いのか」を理解できると、性能問題を未然に防げます。コーディング面接でも頻出のテーマです。
Q. 計算量はどう求めれば良いですか？
A. ループのネストごとに掛け算する、再帰なら漸化式から解く、というのが基本です。Big-O 表記は定数倍と低次の項を無視するため、n の指数（n²、n log n など）に注目してください。最悪・平均・最良の 3 つを意識すると説得力が増します。
Q. 覚えるべき定番アルゴリズムは何ですか？
A. 二分探索、クイックソート/マージソート、BFS/DFS、ダイクストラ、DP の基本問題（フィボナッチ・ナップサック）が必修です。これらを「白紙から書ける」状態にすると、応用問題が一気に解けるようになります。
次のレッスン
次は 第1章まとめクイズ — 再帰の基礎 で、最大公約数を gcd(a, b) = gcd(b, a % b) の漸化式で求める を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- ユークリッド互除法 の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. ユークリッド互除法 とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 関数
gcd(a, b)を実装し、最大公約数を整数で返す - for / while / 組み込み math.gcd を使わず、必ず再帰で実装する
- 基底ケースは b == 0 のとき a を返す
入出力例
test-cases.txt
gcd(12, 18) → 6
gcd(18, 12) → 6
gcd(7, 13) → 1
gcd(100, 25) → 25
gcd(48, 36) → 12
gcd(1, 1) → 1