ユークリッドの互除法：GCD を O(log n) で求めるアルゴリズム

2026年4月26日約4分

GCD（最大公約数）と LCM（最小公倍数）は中学校で習う概念ですが、コンピュータで効率的に計算するには ユークリッドの互除法 という古典的なアルゴリズムが活躍します。本記事ではその仕組みと実装を整理します。

GCD と LCM：定義と関係

GCD（Greatest Common Divisor）：2 つの整数の両方を割り切る最大の正整数
LCM（Least Common Multiple）：2 つの整数の両方の倍数になる最小の正整数

両者の関係：

GCD(a, b) × LCM(a, b) = a × b

GCD が分かれば LCM は割り算で求められます。なので GCD を効率的に求めるアルゴリズムが中心課題。

ナイーブ解：素因数分解

「両方を素因数分解して、共通因子を取る」方法は数学的には自然ですが、計算コストが大きい。素因数分解自体が大きな数では現実的に困難（RSA 暗号がこれに依存）。

実用には別のアプローチが必要でした。

ユークリッドの互除法

紀元前 300 年頃のユークリッドの『原論』に記述された、世界最古級のアルゴリズム。

鍵となる性質：

GCD(a, b) = GCD(b, a mod b)   （b ≠ 0 のとき）
GCD(a, 0) = a

「a を b で割った余り」に置き換えても GCD は変わらない、という性質を再帰的に使います。

例：GCD(48, 36)

GCD(48, 36)
= GCD(36, 48 mod 36) = GCD(36, 12)
= GCD(12, 36 mod 12) = GCD(12, 0)
= 12

3 ステップで解決。

例：GCD(1071, 462)

GCD(1071, 462)
= GCD(462, 1071 mod 462) = GCD(462, 147)
= GCD(147, 462 mod 147) = GCD(147, 21)
= GCD(21, 147 mod 21) = GCD(21, 0)
= 21

4 ステップ。値が大きくても少ない反復で収束します。

計算量：O(log n)

ユークリッドの互除法の反復回数は 入力の桁数に対して対数的です。具体的には：

入力 a, b に対して反復回数は O(log(min(a, b)))
1 反復は除算 1 回 ≒ O(1)（多倍長整数なら O((log n)²)）

最悪ケースは 連続するフィボナッチ数：GCD(F(n+1), F(n)) がちょうど n 反復で解ける。これは Lamé の定理として知られています。

実装：再帰版

function gcd(a, b) {
	if (b === 0) return a;
	return gcd(b, a % b);
}

数行で書けます。スタック深度も O(log n) なので深すぎないはず。

実装：ループ版

function gcd(a, b) {
	while (b !== 0) {
		[a, b] = [b, a % b];
	}
	return a;
}

末尾再帰の最適化が効かない言語では、ループ版が安全。

LCM の実装

GCD さえあれば：

function lcm(a, b) {
	return (a / gcd(a, b)) * b;
}

a * b / gcd だと中間値がオーバーフローしやすいので、先に割ってから掛けるのが定石です。

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

GCD だけでなく、a × x + b × y = gcd(a, b) を満たす整数 x, y も同時に求める版。RSA 暗号の鍵生成や、モジュラ逆元の計算で使われます。

function extendedGcd(a, b) {
	if (b === 0) return { g: a, x: 1, y: 0 };
	const { g, x: x1, y: y1 } = extendedGcd(b, a % b);
	return { g, x: y1, y: x1 - Math.floor(a / b) * y1 };
}

3 つ以上の数の GCD

GCD は結合的：

GCD(a, b, c) = GCD(GCD(a, b), c)

なので、配列に reduce で適用：

function gcdAll(arr) {
	return arr.reduce(gcd);
}

用途

分数の約分：分母と分子の GCD で割る
暗号：RSA の鍵生成（拡張 GCD）
比の計算：「12 : 18」を最簡比 2 : 3 にする
アスペクト比：1920×1080 の最簡比は 16 : 9（GCD = 120）
モジュラ算術：合同式の解法

実装で注意する点

負の数：-12 % 5 は言語によって -2 か 3。GCD は正の数で定義されるので絶対値を取る
0 の扱い：GCD(0, 0) は数学的には未定義だが、慣習で 0 を返す実装が多い
大きな数：BigInt を使うか、多倍長整数ライブラリを使う

まとめ

ユークリッドの互除法は紀元前から使われる古典アルゴリズム
GCD(a, b) = GCD(b, a mod b) の繰り返しで高速に求まる
計算量は O(log n)
LCM は GCD から導出可能
拡張版は RSA など暗号で必須

GCD と LCM を試したいときは、本サイトの GCD・LCM 計算機が使えます。複数の数値を入力して結果を確認できます。