最大公約数（GCD）と最小公倍数（LCM）の求め方｜素因数分解とユークリッドの互除法
算数・数学で登場する「最大公約数（GCD）」と「最小公倍数（LCM）」。分数の通分や約分で必要になりますが、大きな数になると手計算が面倒です。この記事では2つの求め方と実際の使いどころをまとめます。
最大公約数（GCD）とは
最大公約数（GCD: Greatest Common Divisor）は、2つ以上の整数に共通する約数のうち最大のものです。たとえば12と18の約数はそれぞれ以下の通りです。
| 数 | 約数 |
|---|---|
| 12 | 1, 2, 3, 4, 6, 12 |
| 18 | 1, 2, 3, 6, 9, 18 |
共通の約数は 1, 2, 3, 6 で、最大のものが GCD(12, 18) = 6 です。
最小公倍数（LCM）とは
最小公倍数（LCM: Least Common Multiple）は、2つ以上の整数に共通する倍数のうち最小のものです。12と18の場合、共通の倍数は36, 72, 108…となり、LCM(12, 18) = 36 です。
素因数分解で求める方法
それぞれを素因数分解して計算します。
| 数 | 素因数分解 |
|---|---|
| 12 | 2² × 3 |
| 18 | 2 × 3² |
- GCDは各素因数の最小指数の積：2¹ × 3¹ = 6
- LCMは各素因数の最大指数の積：2² × 3² = 36
素因数分解が分かれば2つを同時に求められますが、大きな数になると分解自体が大変です。
ユークリッドの互除法（大きな数に強い）
ユークリッドの互除法は「大きい方を小さい方で割ったあまりを使って繰り返す」だけでGCDを求めるアルゴリズムです。
| ステップ | 計算 | あまり |
|---|---|---|
| ① | 18 ÷ 12 = 1 | あまり 6 |
| ② | 12 ÷ 6 = 2 | あまり 0 |
あまりが0になったときの割る数が GCD です。GCD(18, 12) = 6。
LCMは GCD が求まれば LCM = a × b ÷ GCD(a, b) で計算できます。12 × 18 ÷ 6 = 36。
3つ以上の数への拡張
3つ以上の場合は2つずつ順番に計算します。
- GCD(12, 18, 24) → GCD(GCD(12, 18), 24) = GCD(6, 24) = 6
- LCM(12, 18, 24) → LCM(LCM(12, 18), 24) = LCM(36, 24) = 72
実際の使いどころ
| 場面 | 使うもの | 例 |
|---|---|---|
| 分数の約分 | GCD | 12/18 を約分 → GCD=6 → 2/3 |
| 分数の通分 | LCM | 1/12 + 1/18 → LCM=36 → 3/36 + 2/36 |
| 周期が異なるものが重なるとき | LCM | 3日ごとと4日ごとのイベントが次に重なるのは12日後 |
| 等しく分ける | GCD | 12個と18個を同じ数ずつ最大何グループに分けられるか → 6グループ |
GCD・LCMを計算するツール
複数の整数（2個以上）を入力するだけで最大公約数と最小公倍数をすぐ計算できるGCD・LCM計算ツールを使うと、手計算なしでどんな大きな数でも素早く確認できます。
プログラムで求める
ユークリッドの互除法は数行で実装できます。再帰でも繰り返しでも書けますが、考え方は同じです。
const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
const lcm = (a, b) => (a / gcd(a, b)) * b;
// 3つ以上は順に畳み込む
const gcdAll = (arr) => arr.reduce(gcd);
const lcmAll = (arr) => arr.reduce(lcm);最小公倍数を求めるとき、a * b / gcd(a, b) と書くと、大きな数で桁があふれることがあります。先に割ってから掛ける (a / gcd(a, b)) * b の順にしておくと安全です。
互いに素とは
最大公約数が1になる2つの数の関係を「互いに素」と呼びます。8と15、9と16などが該当します。互いに素であれば、最小公倍数は2数の積そのものになります（8と15なら120）。
この性質は暗号技術でも使われており、RSA暗号では互いに素である数の組み合わせが鍵の生成に用いられています。
身近な計算例
- 周期の重なり：3日ごとの習い事と4日ごとの当番が重なるのは12日ごと（最小公倍数）
- 均等に分ける：12個と18個のお菓子を余りなく同じ数ずつ配れる最大人数は6人（最大公約数）
- タイル敷き：縦120cm・横180cmの床を正方形のタイルで敷き詰めるとき、最大のタイルは1辺60cm
- 歯車：歯数が異なる2つの歯車が元の位置に戻るまでの回転数は、歯数の最小公倍数から求まる
分数の計算での使い分け
約分するときは分子と分母の最大公約数で割ります。18/24 なら最大公約数6で割って 3/4 です。
通分するときは分母の最小公倍数にそろえます。1/6 + 1/8 なら、6と8の最小公倍数24にそろえて 4/24 + 3/24 = 7/24 となります。「約分はGCD、通分はLCM」と覚えると混乱しません。