ユークリッドの互除法とは？わかりやすく解説【最大公約数の求め方と実装例】
テックジム東京本校では、情報科目の受験対策指導もご用意しております。
目次
ユークリッドの互除法とは
ユークリッドの互除法（Euclidean Algorithm）は、2つの整数の**最大公約数（GCD: Greatest Common Divisor）**を効率的に求めるアルゴリズムです。紀元前300年頃、古代ギリシャの数学者ユークリッドが著書『原論』で記述したことからこの名前が付けられました。
このアルゴリズムは、現代でもプログラミングや暗号理論など、さまざまな分野で活用されている非常に重要な数学的手法です。
ユークリッドの互除法の特徴
- 高速: 大きな数でも効率的に計算できる
- シンプル: アルゴリズムが非常に単純
- 確実: 必ず最大公約数を求められる
- 古典的: 2300年以上前から知られる最古のアルゴリズムの一つ
最大公約数（GCD）とは
最大公約数を理解することが、ユークリッドの互除法を理解する第一歩です。
定義
**最大公約数（GCD）**とは、2つ以上の整数に共通する約数のうち、最も大きいものを指します。
例
-
12と18の最大公約数は6
- 12の約数: 1, 2, 3, 4, 6, 12
- 18の約数: 1, 2, 3, 6, 9, 18
- 共通する約数: 1, 2, 3, 6 → 最大は6
-
48と60の最大公約数は12
- 48の約数: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
- 60の約数: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
- 共通する約数: 1, 2, 3, 4, 6, 12 → 最大は12
ユークリッドの互除法の原理
ユークリッドの互除法は、以下の性質を利用しています。
基本原理
2つの整数aとb（a ≥ b）について、以下が成り立ちます:
GCD(a, b) = GCD(b, a mod b)
ここで、a mod bはaをbで割った余りを表します。
この操作を、余りが0になるまで繰り返します。余りが0になったとき、その時の割る数が最大公約数となります。
アルゴリズムの手順
- 大きい方の数を小さい方の数で割り、余りを求める
- 小さい方の数を、先ほどの余りで割り、余りを求める
- 余りが0になるまで、この操作を繰り返す
- 余りが0になったとき、その直前の余り（割る数）が最大公約数
なぜこれが成り立つのか
数学的な証明の要点:
aとbの最大公約数をgとすると、a = gm、b = gnと表せます（mとnは互いに素）。
a = bq + r（qは商、rは余り）と表すと、 r = a – bq = gm – gnq = g(m – nq)
つまり、rもgで割り切れます。これは、GCD(a, b) = GCD(b, r)が成り立つことを意味します。
具体的な計算例
例1: 48と18の最大公約数
ステップごとに計算してみましょう。
ステップ1: 48 ÷ 18 = 2 余り 12
→ GCD(48, 18) = GCD(18, 12)
ステップ2: 18 ÷ 12 = 1 余り 6
→ GCD(18, 12) = GCD(12, 6)
ステップ3: 12 ÷ 6 = 2 余り 0
→ GCD(12, 6) = 6
答え: 最大公約数は6
例2: 1071と462の最大公約数
ステップ1: 1071 ÷ 462 = 2 余り 147
→ GCD(1071, 462) = GCD(462, 147)
ステップ2: 462 ÷ 147 = 3 余り 21
→ GCD(462, 147) = GCD(147, 21)
ステップ3: 147 ÷ 21 = 7 余り 0
→ GCD(147, 21) = 21
答え: 最大公約数は21
例3: 互いに素な数（13と17）
ステップ1: 17 ÷ 13 = 1 余り 4
→ GCD(17, 13) = GCD(13, 4)
ステップ2: 13 ÷ 4 = 3 余り 1
→ GCD(13, 4) = GCD(4, 1)
ステップ3: 4 ÷ 1 = 4 余り 0
→ GCD(4, 1) = 1
答え: 最大公約数は1（互いに素）
プログラム実装例
ユークリッドの互除法は、プログラミングで簡潔に実装できます。
Python実装
反復版（whileループ）
def gcd(a, b):
"""ユークリッドの互除法で最大公約数を求める（反復版）"""
while b != 0:
a, b = b, a % b
return a
# 使用例
print(gcd(48, 18)) # 出力: 6
print(gcd(1071, 462)) # 出力: 21
print(gcd(13, 17)) # 出力: 1
再帰版
def gcd_recursive(a, b):
"""ユークリッドの互除法で最大公約数を求める（再帰版）"""
if b == 0:
return a
return gcd_recursive(b, a % b)
# 使用例
print(gcd_recursive(48, 18)) # 出力: 6
print(gcd_recursive(1071, 462)) # 出力: 21
JavaScript実装
// 反復版
function gcd(a, b) {
while (b !== 0) {
let temp = b;
b = a % b;
a = temp;
}
return a;
}
// 再帰版
function gcdRecursive(a, b) {
if (b === 0) {
return a;
}
return gcdRecursive(b, a % b);
}
// 使用例
console.log(gcd(48, 18)); // 出力: 6
console.log(gcdRecursive(1071, 462)); // 出力: 21
Java実装
public class EuclideanAlgorithm {
// 反復版
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 再帰版
public static int gcdRecursive(int a, int b) {
if (b == 0) {
return a;
}
return gcdRecursive(b, a % b);
}
public static void main(String[] args) {
System.out.println(gcd(48, 18)); // 出力: 6
System.out.println(gcdRecursive(1071, 462)); // 出力: 21
}
}
C++実装
#include <iostream>
// 反復版
int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 再帰版
int gcd_recursive(int a, int b) {
if (b == 0) {
return a;
}
return gcd_recursive(b, a % b);
}
int main() {
std::cout << gcd(48, 18) << std::endl; // 出力: 6
std::cout << gcd_recursive(1071, 462) << std::endl; // 出力: 21
return 0;
}
応用例と活用場面
ユークリッドの互除法は、さまざまな場面で活用されています。
1. 分数の約分
分数を最も簡単な形に約分する際に使用します。
def simplify_fraction(numerator, denominator):
"""分数を約分する"""
g = gcd(numerator, denominator)
return numerator // g, denominator // g
# 例: 48/18 を約分
print(simplify_fraction(48, 18)) # 出力: (8, 3)
2. 最小公倍数（LCM）の計算
最小公倍数は、以下の公式で求められます:
LCM(a, b) = (a × b) / GCD(a, b)
def lcm(a, b):
"""最小公倍数を求める"""
return abs(a * b) // gcd(a, b)
# 例
print(lcm(12, 18)) # 出力: 36
3. 暗号理論（RSA暗号）
RSA暗号などの公開鍵暗号方式では、互いに素な数を見つける際にユークリッドの互除法が使用されます。
4. モジュラ逆元の計算
拡張ユークリッドの互除法を使用して、モジュラ逆元を計算できます。これは暗号理論やコンピュータサイエンスで重要です。
5. 座標幾何学
2点を通る直線上の格子点の個数を求める際に使用されます。
6. 音楽理論
音程の比率の計算や、和音の分析に応用されることがあります。
計算量と効率性
時間計算量
ユークリッドの互除法の時間計算量は**O(log min(a, b))**です。
これは非常に効率的で、大きな数に対しても高速に動作します。例えば、フィボナッチ数のような最悪のケースでも、入力の桁数に対して対数的な回数で終了します。
他の方法との比較
素朴な方法（試し割り）
def gcd_naive(a, b):
"""素朴な方法で最大公約数を求める"""
result = 1
for i in range(1, min(a, b) + 1):
if a % i == 0 and b % i == 0:
result = i
return result
この方法の時間計算量はO(min(a, b))で、ユークリッドの互除法よりはるかに遅くなります。
拡張ユークリッドの互除法
拡張ユークリッドの互除法は、基本的なアルゴリズムを拡張したもので、以下の式を満たす整数xとyを求めます:
ax + by = GCD(a, b)
実装例（Python）
def extended_gcd(a, b):
"""拡張ユークリッドの互除法"""
if b == 0:
return a, 1, 0
else:
gcd, x1, y1 = extended_gcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return gcd, x, y
# 使用例
gcd, x, y = extended_gcd(48, 18)
print(f"GCD: {gcd}") # 出力: GCD: 6
print(f"{48} * {x} + {18} * {y} = {gcd}") # 出力: 48 * 1 + 18 * -2 = 6
よくある質問（FAQ）
Q1: ユークリッドの互除法は負の数でも使えますか？
A: はい、使えます。ただし、通常は絶対値を使って計算します。
def gcd(a, b):
a, b = abs(a), abs(b)
while b != 0:
a, b = b, a % b
return a
Q2: 3つ以上の数の最大公約数はどう求めますか？
A: 順番に2つずつ計算します。
from functools import reduce
def gcd_multiple(*numbers):
"""複数の数の最大公約数を求める"""
return reduce(gcd, numbers)
# 使用例
print(gcd_multiple(48, 18, 30)) # 出力: 6
Q3: Pythonの標準ライブラリにGCDの関数はありますか？
A: はい、math.gcd()関数があります（Python 3.5以降）。
import math
print(math.gcd(48, 18)) # 出力: 6
まとめ
ユークリッドの互除法は、2300年以上前から知られる古典的なアルゴリズムでありながら、現代でも広く活用されている効率的な手法です。
この記事のポイント
- ユークリッドの互除法は最大公約数を効率的に求めるアルゴリズム
- 割り算の余りを繰り返し利用する単純な仕組み
- 時間計算量は**O(log min(a, b))**と非常に効率的
- プログラミング実装が簡潔で、再帰版・反復版どちらも可能
- 分数の約分、最小公倍数の計算、暗号理論など応用範囲が広い
プログラミングの基礎として、また数学的思考を養う題材として、ユークリッドの互除法を理解することは非常に有益です。ぜひ実際にコードを書いて、動作を確認してみてください。
参考資料
- ユークリッド『原論』第7巻
- Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms
- 各プログラミング言語の公式ドキュメント
関連キーワード: 最大公約数, GCD, アルゴリズム, 整数論, プログラミング, 数学, 約分, 最小公倍数, LCM, RSA暗号
■らくらくPython塾 – 読むだけでマスター
【現役エンジニア歓迎】プログラミング学習お悩み相談会
【情報I】受験対策・お悩み相談会（オンライン・無料）
【オンライン無料】ゼロから始めるPython爆速講座
■テックジム東京本校
格安のプログラミングスクールといえば「テックジム」。
講義動画なし、教科書なし。「進捗管理とコーチング」で効率学習。
対面型でより早くスキル獲得、月額2万円のプログラミングスクールです。
情報科目の受験対策指導もご用意しております。
