最大公約数・最小公倍数の計算

最終更新: 2026-05-13

定義

最大公約数（GCD〈Greatest Common Divisor〉）は、複数の整数に共通する約数のうち最大のものです。最小公倍数（LCM〈Least Common Multiple〉）は、共通する倍数のうち最小のものです。いずれも 2 つの整数の算術的な関係を端的に表す量です。

12 と 8 を例にとります。

• 12 と 8 の公約数は 1、2、4 です。その中で最大のものは 4 です。
• 12 と 8 の公倍数は 24、48、72、… と続きます。その中で最小のものは 24 です。

ユークリッドの互除法による最大公約数の計算

最大公約数を求める代表的な方法がユークリッドの互除法です。紀元前 300 年頃に著された『原論』で述べられた手法で、現在も効率的な計算手順として使われています。核心となる性質は次の式です。

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

ここで $a \bmod b$ は $a$ を $b$ で割ったときの余りです。余りが 0 になるまで繰り返し、最後に 0 でない余りが最大公約数になります。

例: GCD(48, 18)

ステップ	$a$	$b$	$a \bmod b$
1	48	18	12
2	18	12	6
3	12	6	0

最後に現れた 0 でない余りは 6 なので、GCD(48, 18) = 6 です。

このアルゴリズムのステップ数は、小さいほうの数の桁数の 5 倍を超えないことが知られています。

最大公約数と最小公倍数の恒等式

最大公約数が求まれば、最小公倍数は 1 つの式で計算できます。

$\text{LCM}(a, b) = \frac{a \times b}{\gcd(a, b)}$

これは偶然ではなく、整数の素因数分解の一意性から導かれる定理です。各整数を素数の積とみなすと、最大公約数は各素数の指数の最小値を、最小公倍数は最大値を取ります。両者の積は常に $a \times b$ になります。

例: LCM(12, 8)

$\text{GCD}(12, 8) = 4, \quad \text{LCM}(12, 8) = \frac{12 \times 8}{4} = 24$

確認すると $4 \times 24 = 96 = 12 \times 8$ となり、恒等式が成り立っています。

最大公約数・最小公倍数が役立つ場面

分数の約分

$\dfrac{a}{b}$ を既約分数に約分するには、分子と分母を $\gcd(a, b)$ で割ります。たとえば $\dfrac{12}{8}$ は $\gcd(12, 8) = 4$ で割ると $\dfrac{3}{2}$ になります。

分数の加算

$\dfrac{1}{12} + \dfrac{1}{8}$ を計算するには、最小公倍数 $\text{LCM}(12, 8) = 24$ を通分の分母として使います。

$\frac{1}{12} + \frac{1}{8} = \frac{2}{24} + \frac{3}{24} = \frac{5}{24}$

周期の問題

2 つの事象がそれぞれ $a$ 日ごと・$b$ 日ごとに繰り返される場合、次に同時に起こるのは $\text{LCM}(a, b)$ 日後です。歯車の歯数比、タイル模様の周期、天体の会合周期などに最小公倍数が現れるのはこのためです。

暗号理論

ユークリッドの互除法は RSA 暗号の中核となる演算で、選んだ鍵指数が法のオイラー関数と互いに素であることを最大公約数で確認するために使われます。

特殊なケース

• GCD(a, 0) = a（a は任意の正の整数）: すべての整数は 0 を割り切るという定義から自然に導かれる、互除法の基底ケースです。
• 互いに素な数: 最大公約数 = 1 で最小公倍数 = a × b です。例として GCD(7, 13) = 1、LCM(7, 13) = 91。
• 同じ数の場合: GCD(n, n) = n、LCM(n, n) = n です。

公式早見表

性質	式
ユークリッドの互除法	$\gcd(a, b) = \gcd(b,\ a \bmod b)$
最大公約数から最小公倍数	$\text{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$
恒等式	$\gcd(a,b) \times \text{lcm}(a,b) = a \times b$
分数の約分	分子と分母を $\gcd$ で割る
通分の分母	2 つの分母の $\text{lcm}$ を使う

よくある質問 (FAQ)

最大公約数とは何ですか？

最大公約数（GCD）とは、2 つの整数をどちらも割り切ることができる正の整数のうち最大のものです。たとえば GCD(12, 8) = 4 で、これは 12 と 8 の両方を余りなく割り切れる最大の数です。

最小公倍数とは何ですか？

最小公倍数（LCM）とは、2 つの整数の倍数に共通する最小の正の整数です。たとえば LCM(12, 8) = 24 で、これは 12 の倍数かつ 8 の倍数である最小の数です。

最大公約数と最小公倍数にはどんな関係がありますか？

任意の 2 つの正の整数 a と b に対して、GCD(a, b) × LCM(a, b) = a × b が成り立ちます。つまり、一方が分かればもう一方を導けます（LCM = a × b ÷ GCD）。この関係があるため、2 つの値をまとめて計算するのが便利です。