2つ以上の整数に「共通する約数」と「共通する倍数」を見つける技術は、整数問題の基盤です。
素因数分解を使った求め方を原理から理解し、GCDとLCMの間に成り立つ美しい関係式を証明します。
9-1で学んだ素因数分解は、整数を素数の積に分解する技術でした。 この技術が最も威力を発揮するのが、最大公約数（GCD）と最小公倍数（LCM）の計算です。
まず基本的な用語を確認しましょう。 2つ以上の整数に共通な約数を公約数といい、公約数の中で最も大きいものを最大公約数（Greatest Common Divisor, GCD）といいます。 最大公約数は記号で $\gcd(a, b)$ と書きます。
たとえば、$12$ の約数は $\{1, 2, 3, 4, 6, 12\}$、$18$ の約数は $\{1, 2, 3, 6, 9, 18\}$ です。 共通する約数（公約数）は $\{1, 2, 3, 6\}$ で、最大のものは $6$ です。 つまり $\gcd(12, 18) = 6$ です。
約数をすべて書き出す方法は、数が大きくなると現実的ではありません。 そこで、素因数分解を活用します。
$12 = 2^2 \times 3$ と $18 = 2 \times 3^2$ を見比べてみましょう。 最大公約数は、共通する素因数について、指数の小さい方をとって掛け合わせたものです。
素因数 $2$：$12$ では指数 $2$、$18$ では指数 $1$ → 小さい方は $1$
素因数 $3$：$12$ では指数 $1$、$18$ では指数 $2$ → 小さい方は $1$
よって $\gcd(12, 18) = 2^1 \times 3^1 = 6$ です。
素因数分解とは、整数を素数の「在庫リスト」として表すことです。 $12 = 2^2 \times 3^1$ は「素数2を2個、素数3を1個持っている」という意味です。
最大公約数は、2つの数が共通して持っている素数を、少ない方の個数だけ取り出す操作です。 集合の「共通部分（$\cap$）」と同じ発想です。
だから、最大公約数は共通な素因数について指数の最小値をとるのです。
$a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$、$b = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k}$ のとき
$$\gcd(a, b) = p_1^{\min(\alpha_1, \beta_1)} \cdot p_2^{\min(\alpha_2, \beta_2)} \cdots p_k^{\min(\alpha_k, \beta_k)}$$
$504$ と $240$ の最大公約数を求めてみましょう。
Step 1：素因数分解する。
$504 = 2^3 \times 3^2 \times 7$、$240 = 2^4 \times 3 \times 5$
Step 2：共通な素因数について、指数の小さい方をとる。
素因数 $2$：$\min(3, 4) = 3$
素因数 $3$：$\min(2, 1) = 1$
素因数 $5$：$504$ には含まれない（指数 $0$） → $\min(0, 1) = 0$
素因数 $7$：$240$ には含まれない（指数 $0$） → $\min(1, 0) = 0$
結論：$\gcd(504, 240) = 2^3 \times 3^1 = 24$
2つの整数 $a, b$ の最大公約数が $1$ であるとき、$a$ と $b$ は互いに素であるといいます。 これは「$a$ と $b$ が共通の素因数を1つも持たない」ことを意味します。
たとえば $15 = 3 \times 5$ と $28 = 2^2 \times 7$ は共通する素因数がないので互いに素です。 互いに素であるかどうかは、整数の問題を解く上で極めて重要な判断基準になります。
✕ 誤：$6$ と $35$ は互いに素？ → $6$ は素数じゃないから違う
○ 正：$6 = 2 \times 3$、$35 = 5 \times 7$。共通する素因数がないので $\gcd(6, 35) = 1$。互いに素です。
「互いに素」は2つの数の関係を表す言葉であり、個々の数が素数であるかどうかとは無関係です。 合成数同士でも互いに素になりえます。
✕ 誤：$84 = 2^2 \times 3 \times 7$ と $126 = 2 \times 3^2 \times 7$ の GCD を $2 \times 3 \times 7 = 42$ と答える。
これは正解ですが、もし素因数分解の段階で $84 = 4 \times 21$ のまま止めてしまうと、共通する素因数を正しく比較できません。
○ 正：必ずすべての因数が素数になるまで分解してから比較しましょう。 素因数分解が正しくなければ、GCDもLCMも正しく求められません。
$\gcd(a, b)$ には美しい幾何学的解釈があります。 横 $a$、縦 $b$ の長方形を、同じ大きさの正方形で隙間なく敷き詰めるとき、 使える最大の正方形の1辺の長さが $\gcd(a, b)$ です。
たとえば、横 $12$、縦 $8$ の長方形は、1辺 $4 = \gcd(12, 8)$ の正方形で敷き詰められます。 この考え方は、ユークリッドの互除法（9-2で学習）の幾何学的な背景でもあります。
次に最小公倍数（Least Common Multiple, LCM）を学びましょう。 2つ以上の整数に共通な正の倍数を公倍数といい、公倍数の中で最も小さいものを最小公倍数といいます。 記号では $\text{lcm}(a, b)$ と書きます。
たとえば、$4$ の正の倍数は $\{4, 8, 12, 16, 20, 24, \ldots\}$、$6$ の正の倍数は $\{6, 12, 18, 24, \ldots\}$ です。 共通する倍数（公倍数）は $\{12, 24, 36, \ldots\}$ で、最小のものは $12$ です。 つまり $\text{lcm}(4, 6) = 12$ です。
GCDが「共通部分（$\cap$）」だったのに対し、LCMは「和集合（$\cup$）」です。
$a$ の倍数であるためには、$a$ のすべての素因数を少なくとも $a$ と同じ個数だけ含んでいなければなりません。 $b$ の倍数であるためにも同様です。
よって、両方の倍数であるためには、各素因数を多い方の個数だけ持つ必要があります。 これが「最小」の公倍数です。
$a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k}$、$b = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdots p_k^{\beta_k}$ のとき
$$\text{lcm}(a, b) = p_1^{\max(\alpha_1, \beta_1)} \cdot p_2^{\max(\alpha_2, \beta_2)} \cdots p_k^{\max(\alpha_k, \beta_k)}$$
先ほどの $504 = 2^3 \times 3^2 \times 7$ と $240 = 2^4 \times 3 \times 5$ の最小公倍数を求めましょう。
素因数 $2$：$\max(3, 4) = 4$
素因数 $3$：$\max(2, 1) = 2$
素因数 $5$：$\max(0, 1) = 1$
素因数 $7$：$\max(1, 0) = 1$
よって $\text{lcm}(504, 240) = 2^4 \times 3^2 \times 5 \times 7 = 16 \times 9 \times 5 \times 7 = 5040$ です。
GCDとLCMには、以下の重要な性質があります。
つまり、公約数を求めたければ GCD の約数を列挙すればよく、公倍数を求めたければ LCM の倍数を列挙すればよいのです。
✕ 誤：$504 = 2^3 \times 3^2 \times 7$ と $240 = 2^4 \times 3 \times 5$ のLCMを求めるとき、 共通する素因数 $2$ と $3$ だけに着目して $2^4 \times 3^2 = 144$ と答える。
○ 正：LCMではすべての素因数を含めます。 $504$ にしかない $7$ も、$240$ にしかない $5$ も必要です。 $\text{lcm} = 2^4 \times 3^2 \times 5 \times 7 = 5040$。
GCDは「共通する素因数だけ」ですが、LCMは「すべての素因数」を使います。この違いを混同しないでください。
大学の代数学では、GCDとLCMは束（lattice）と呼ばれる数学的構造の一例として扱われます。 自然数全体を「割り切る関係（$a \mid b$）」で順序づけると、GCDは下限（meet）、LCMは上限（join）に相当します。
集合論での $\cap$（共通部分）と $\cup$（和集合）が束をなすのと同じ構造です。 「$\min$ と $\max$」「$\cap$ と $\cup$」「GCD と LCM」は、すべて同じ抽象的パターンの具体例なのです。
GCDとLCMの間には、驚くほどシンプルで美しい関係が成り立ちます。 2つの自然数 $a, b$ について、
$$\gcd(a, b) \times \text{lcm}(a, b) = a \times b$$この関係式は、整数問題を解く上で非常に強力な道具です。 なぜ成り立つのかを、2つの方法で理解しましょう。
任意の2つの数 $\alpha, \beta$ について、$\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$ が成り立ちます。
GCDでは各素因数の指数に $\min$ を、LCMでは $\max$ をとりました。 掛け算は指数の足し算なので、
$\gcd(a,b) \times \text{lcm}(a,b)$ の各素因数の指数 $= \min(\alpha_i, \beta_i) + \max(\alpha_i, \beta_i) = \alpha_i + \beta_i$
一方、$a \times b$ の各素因数の指数 $= \alpha_i + \beta_i$
両者が一致するのは当然なのです。$\min + \max$ の恒等式が本質です。
$a = \prod p_i^{\alpha_i}$、$b = \prod p_i^{\beta_i}$ とする（一方に含まれない素因数は指数を $0$ とする）。
定義より、$\gcd(a,b) = \prod p_i^{\min(\alpha_i, \beta_i)}$、$\text{lcm}(a,b) = \prod p_i^{\max(\alpha_i, \beta_i)}$。
$\gcd(a,b) \times \text{lcm}(a,b) = \prod p_i^{\min(\alpha_i, \beta_i) + \max(\alpha_i, \beta_i)}$
ここで、任意の非負整数 $\alpha, \beta$ について $\min(\alpha, \beta) + \max(\alpha, \beta) = \alpha + \beta$ が成り立つ。
（$\alpha \leq \beta$ なら $\min = \alpha, \max = \beta$ で和は $\alpha + \beta$。$\alpha > \beta$ でも同様。）
よって、$\gcd(a,b) \times \text{lcm}(a,b) = \prod p_i^{\alpha_i + \beta_i} = \prod p_i^{\alpha_i} \times \prod p_i^{\beta_i} = a \times b$ ■
もう1つの理解の仕方を紹介します。 $\gcd(a, b) = g$ とおくと、$a = ga'$、$b = gb'$ と書けて、$a'$ と $b'$ は互いに素です（$\gcd(a', b') = 1$）。
このとき、$\text{lcm}(a, b) = ga'b'$ です。なぜなら、$ga'b'$ は $a = ga'$ の倍数であり（$b'$ 倍）、 $b = gb'$ の倍数でもあり（$a'$ 倍）、$a'$ と $b'$ が互いに素であることから、これより小さい公倍数は存在しないからです。
よって、$\gcd(a,b) \times \text{lcm}(a,b) = g \times ga'b' = g^2 a'b' = (ga')(gb') = ab$ です。
2つの自然数 $a, b$ について
$$\gcd(a, b) \times \text{lcm}(a, b) = ab$$
特に、$\gcd(a,b) = g$、$a = ga'$、$b = gb'$（$a', b'$ は互いに素）とおくと
$$\text{lcm}(a, b) = ga'b' = \frac{ab}{g}$$
この公式は、GCDやLCMの条件から2つの自然数を決定する問題で活躍します。 $\gcd(a,b) = g$ のとき、$a = ga'$、$b = gb'$（$a'$ と $b'$ は互いに素）とおく手法は定石です。
✕ 誤：積が $720$、最大公約数が $6$ の2自然数を求めるとき、$a = 6a', b = 6b'$ とおいて $36a'b' = 720$、$a'b' = 20$ を解く。$(a', b') = (1, 20), (2, 10), (4, 5), (5, 4), (10, 2), (20, 1)$ の全6組を答える。
○ 正：$a'$ と $b'$ は互いに素でなければなりません。$\gcd(2, 10) = 2 \neq 1$、$\gcd(4, 5) = 1$。 条件を満たすのは $(a', b') = (1, 20), (4, 5), (5, 4), (20, 1)$ のみです。 よって $(a, b) = (6, 120), (24, 30), (30, 24), (120, 6)$。
$a = ga', b = gb'$ という分解は、2つの数から「共通因数 $g$ を外に出す」操作です。 残った $a'$ と $b'$ は互いに素 ── つまり、$a$ と $b$ の「本質的に異なる部分」だけが残ります。
この「GCDでくくり出す」テクニックは、整数問題の至るところで使われます。 2数の関係を調べるときは、まずGCDで割って互いに素な部分を取り出すのが基本戦略です。
$a$ と $b$ という2つの数が持つ「素因数の情報」は、GCDとLCMに分配されます。 GCDには「共通部分」、LCMには「全体」が入り、合わせると元の情報量 $ab$ と一致する。 これは情報理論的に言えば「情報の保存則」のようなものです。
大学数学では、整数環 $\mathbb{Z}$ における $\gcd$ と $\text{lcm}$ は、 イデアルの和（$\mathfrak{a} + \mathfrak{b}$）と交わり（$\mathfrak{a} \cap \mathfrak{b}$）に対応します。 $\gcd \cdot \text{lcm} = ab$ は、この代数的構造の反映です。
3つ以上の数のGCDとLCMも、素因数分解を使えば同じ原理で求められます。 ただし、2数の場合に成り立った公式がそのまま使えない点に注意が必要です。
3つの数 $a, b, c$ の最大公約数は、各素因数の指数の最小値を、最小公倍数は最大値をとります。 2数の場合と全く同じ原理です。
たとえば、$84 = 2^2 \times 3 \times 7$、$126 = 2 \times 3^2 \times 7$、$630 = 2 \times 3^2 \times 5 \times 7$ のとき、
$\gcd(84, 126, 630)$：各素因数の指数の最小値をとると
$2^{\min(2,1,1)} \times 3^{\min(1,2,2)} \times 5^{\min(0,0,1)} \times 7^{\min(1,1,1)} = 2^1 \times 3^1 \times 7^1 = 42$
$\text{lcm}(84, 126, 630)$：各素因数の指数の最大値をとると
$2^{\max(2,1,1)} \times 3^{\max(1,2,2)} \times 5^{\max(0,0,1)} \times 7^{\max(1,1,1)} = 2^2 \times 3^2 \times 5 \times 7 = 1260$
素因数分解が面倒な場合は、すだれ算（連除法）を使う方法もあります。 2数の場合は、共通する素因数で順に割っていき、左に並んだ素因数の積がGCD、GCDに下の2数のLCMを掛けたものが全体のLCMになります。
3数の場合は少し注意が必要です。GCDを求めるときは3数すべてを割れる素数で割りますが、 LCMを求めるときは2数以上を割れる素数で割り続けます。
✕ 誤：「2数で $\gcd(a,b) \times \text{lcm}(a,b) = ab$ が成り立つから、 3数でも $\gcd(a,b,c) \times \text{lcm}(a,b,c) = abc$ が成り立つ」
○ 正：反例を確認しましょう。$a = 4, b = 6, c = 12$ のとき、 $\gcd = 2$、$\text{lcm} = 12$。$\gcd \times \text{lcm} = 24$ ですが、$abc = 288$。一致しません。
$\gcd \times \text{lcm} = ab$ は2数限定の公式です。3数以上では、素因数の「重複」の構造が複雑になるため、単純な積の関係は成り立ちません。 3数以上の問題では、素因数分解に立ち返って直接求めるのが確実です。
3数のGCDは、$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$ と段階的に計算できます。 つまり、まず2数のGCDを求め、その結果と3番目の数のGCDを求めればよいのです。 LCMについても同様に $\text{lcm}(a, b, c) = \text{lcm}(\text{lcm}(a, b), c)$ が成り立ちます。
これは素因数分解を考えれば明らかです。$\min(\alpha, \beta, \gamma) = \min(\min(\alpha, \beta), \gamma)$ だからです。
コンピュータサイエンスでは、GCDはユークリッドの互除法（9-2で学習）で高速に計算されます。
Python では math.gcd(a, b) で一発です。
3数以上のGCDも、$\gcd(a, b, c) = \gcd(\gcd(a, b), c)$ を使って再帰的に計算できます。 LCMは $\text{lcm}(a,b) = ab / \gcd(a,b)$ で求めるのが定番です。 暗号理論（RSA暗号）では、大きな素数のLCMを計算することが安全性の鍵を握っています。
ここまで学んだ内容を鳥の目で俯瞰し、全体像を整理しましょう。
| 問題タイプ | 問題の特徴 | 解法のポイント |
|---|---|---|
| A：GCD・LCMの計算 | 2数または3数のGCD/LCMを求める | 素因数分解 → $\min$/$\max$ で指数を決定 |
| B：数の決定 | GCDやLCMの条件から元の数を求める | $a = ga', b = gb'$（互いに素）とおく |
| C：互いに素の証明 | $\gcd(a, b) = 1$ を示す | GCDを $g$ とおいて $g = 1$ を導く |
| D：条件付き数の決定 | 3数のGCD・LCMの条件で数を決定 | 素因数分解で各素因数の指数を調べる |
Q1. $\gcd(72, 108)$ を素因数分解を用いて求めてください。
Q2. $\text{lcm}(72, 108)$ を求めてください（Q1の結果を利用可）。
Q3. 最大公約数と最小公倍数を素因数分解で求めるとき、GCDでは指数に何の関数を使い、LCMでは何を使いますか？
Q4. $15$ と $28$ は互いに素ですか？理由とともに答えてください。
Q5. 3つの数 $a, b, c$ について $\gcd(a,b,c) \times \text{lcm}(a,b,c) = abc$ は成り立ちますか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
次の各組の最大公約数と最小公倍数を求めよ。
(1) $168$ と $252$
(2) $84$, $126$, $630$
(1) 最大公約数 $84$、最小公倍数 $504$
(2) 最大公約数 $42$、最小公倍数 $1260$
方針：素因数分解してから $\min$/$\max$ で求める。
(1) $168 = 2^3 \times 3 \times 7$、$252 = 2^2 \times 3^2 \times 7$
$\gcd = 2^2 \times 3 \times 7 = 84$、$\text{lcm} = 2^3 \times 3^2 \times 7 = 504$
検算：$84 \times 504 = 42336 = 168 \times 252$。✓
(2) $84 = 2^2 \times 3 \times 7$、$126 = 2 \times 3^2 \times 7$、$630 = 2 \times 3^2 \times 5 \times 7$
$\gcd = 2^1 \times 3^1 \times 7^1 = 42$、$\text{lcm} = 2^2 \times 3^2 \times 5 \times 7 = 1260$
和が $192$、最大公約数が $16$ である2つの自然数の組 $(a, b)$（$a \leq b$）をすべて求めよ。
$(a, b) = (16, 176), (32, 160), (48, 144), (64, 128), (80, 112)$
方針：$\gcd(a,b) = 16$ より $a = 16a', b = 16b'$（$a', b'$ は互いに素、$a' \leq b'$）とおく。
$a + b = 16(a' + b') = 192$ より $a' + b' = 12$。
$a' + b' = 12$、$\gcd(a', b') = 1$、$1 \leq a' \leq b'$ を満たす組を探す。
$(a', b') = (1, 11), (5, 7)$ → $\gcd(1, 11) = 1$ ✓、$\gcd(5, 7) = 1$ ✓
$(a', b') = (2, 10)$ → $\gcd = 2$ ✗、$(3, 9)$ → $\gcd = 3$ ✗、$(4, 8)$ → $\gcd = 4$ ✗、$(6, 6)$ → $\gcd = 6$ ✗
⚠️ 訂正：$a' \leq b'$ かつ互いに素なのは $(1, 11), (5, 7)$ の2組。
しかし「$a' + b' = 12$ かつ互いに素」をすべて確認すると $(1,11), (5,7)$ のみ。
$(a,b) = (16, 176), (80, 112)$
⚠️ 再確認：問題文の条件をチェック。和が $192$ で最大公約数が $16$ の自然数の組は $(16, 176), (80, 112)$ の2組（$a \leq b$）。
積が $720$、最大公約数が $6$ であるような2つの自然数 $a, b$（$a \leq b$）をすべて求めよ。
$(a, b) = (6, 120), (24, 30)$
方針：$\gcd(a,b) = 6$ より $a = 6a', b = 6b'$（$a', b'$ は互いに素）とおく。
$ab = 36a'b' = 720$ より $a'b' = 20$。
$a'b' = 20$、$\gcd(a', b') = 1$、$a' \leq b'$ を満たす組を探す。
$20$ の因数分解：$(1, 20), (2, 10), (4, 5)$
$\gcd(1, 20) = 1$ ✓、$\gcd(2, 10) = 2$ ✗、$\gcd(4, 5) = 1$ ✓
$(a', b') = (1, 20), (4, 5)$ → $(a, b) = (6, 120), (24, 30)$
3つの整数 $36, 120, n$ の最大公約数が $6$、最小公倍数が $360$ となるような自然数 $n$ をすべて求めよ。
$n = 6, 18, 30, 54, 90, 270$
方針：$36, 120, n$ を素因数分解し、GCDとLCMの条件から $n$ の素因数の指数を絞り込む。
$36 = 2^2 \times 3^2$、$120 = 2^3 \times 3 \times 5$。
$\gcd = 6 = 2 \times 3$、$\text{lcm} = 360 = 2^3 \times 3^2 \times 5$。
$n = 2^a \times 3^b \times 5^c$（これ以外の素因数は $\text{lcm}$ に含まれないので持てない）とおく。
GCD条件（各指数の $\min$ が $\gcd$ の指数）：
$\min(2, 3, a) = 1$ → $a \leq 1$ すなわち $a = 0$ または $1$。ただし $a = 0$ なら $\min(2, 3, 0) = 0 \neq 1$。よって $a = 1$。
$\min(2, 1, b) = 1$ → $b \geq 1$（$\min(2, 1, b) = \min(1, b)$。$b \geq 1$ なら $\min = 1$。$b = 0$ なら $\min = 0 \neq 1$）。よって $b \geq 1$。
$\min(0, 1, c) = 0$ → $c \geq 0$（$36$ に $5$ が含まれないので $\min$ は自動的に $0$）。これは自動的に成立。
LCM条件（各指数の $\max$ が $\text{lcm}$ の指数）：
$\max(2, 3, a) = 3$ → $a \leq 3$。$a = 1$（GCD条件より）は $3$ 以下なので ✓。
$\max(2, 1, b) = 2$ → $b \leq 2$。GCD条件と合わせて $1 \leq b \leq 2$。ただし $\max(2, 1, b) = \max(2, b)$。$b \leq 2$ なら $\max = 2$。$b = 3$ なら $\max = 3 \neq 2$。よって $b \in \{1, 2\}$。ただし $b \geq 1$ よりそのまま。
$\max(0, 1, c) = 1$ → $c \leq 1$。よって $c \in \{0, 1\}$。
まとめ：$a = 1$、$b \in \{1, 2\}$、$c \in \{0, 1\}$。ただし LCM 条件で $\max(2, 1, b) = 2$ を確認：$b = 1$ → $\max(2,1,1) = 2$ ✓、$b = 2$ → $\max(2,1,2) = 2$ ✓。また $b = 3$ → $\max = 3 \neq 2$ ✗。
さらに $\max(2, 3, 1) = 3$ ✓。GCDの $5$ の指数：$\min(0, 1, c) = 0$ は常に成立。LCMの $5$ の指数：$\max(0, 1, c) = 1$ → $c \leq 1$ ✓。
再検討：$n = 2^1 \times 3^b \times 5^c$ で $b \in \{1, 2, 3\}$、$c \in \{0, 1\}$ のうち LCM 条件を満たすもの。
$b = 3$：$\max(2,1,3) = 3 \neq 2$ ✗。よって $b \in \{1, 2\}$。
残る組合せ：$(b, c) = (1, 0), (1, 1), (2, 0), (2, 1)$
$n = 2 \times 3 = 6$、$n = 2 \times 3 \times 5 = 30$、$n = 2 \times 9 = 18$、$n = 2 \times 9 \times 5 = 90$
⚠️ 再確認：$b = 3$ のケースを改めて。GCD条件 $\min(2,1,3) = 1$ ✓。LCM条件 $\max(2,1,3) = 3 \neq 2$ ✗。よって不適。
実は $n$ は $2, 3, 5$ 以外の素因数を含まない必要がある（LCMに含まれないから）。
答え：$n = 6, 18, 30, 90$