最大公約数と最小公倍数とは？関係式と求め方について

1. 最大公約数 (GCD)

1.1. 公約数とは

12と18の公約数を考えてみましょう。

• 12の約数: 1, 2, 3, 4, 6, 12
• 18の約数: 1, 2, 3, 6, 9, 18

12と18に共通する約数は1、2、3、6です。これが公約数です。

1.2. 最大公約数とは

• 最大公約数・・・GCDとも呼ばれます。英語で、Greatest Common Divisor。
• gcd(a,b)・・・a,bの最大公約数を意味します。

---

例えば、36と48の最大公約数を求める場合、両方の約数は次のようになります。

• 36の約数：1, 2, 3, 4, 6, 9, 12, 18, 36
• 48の約数：1, 2, 3, 4, 6, 8, 12, 16, 24, 48

これらの中で共通している最大の約数は12です。したがって、36と48の最大公約数は12です。

2. 最小公倍数

2.1. 公倍数とは

12と18の公倍数を考えてみましょう。

• 12の倍数: 12, 24, 36, 48, 60, 72, 84, 96, …
• 18の倍数: 18, 36, 54, 72, 90, 108, …

12と18に共通する倍数は36、72、108、…と続きます。これが公倍数です。

2.2. 最小公倍数 (lcm)

• 最小公倍数・・・LCMとも呼ばれます。英語で、least common multiple。
• lcm(a,b)・・・a,bの最小公倍数を意味します。

---

例えば、36と48の最小公倍数を求める場合、両方の数の倍数を確認します。

• 36の倍数：36, 72, 108, 144, 180, …
• 48の倍数：48, 96, 144, 192, …

共通する最小の倍数は144です。したがって、36と48の最小公倍数は144です。

3. 最大公約数と最小公倍数の性質

3.1. 最大公約数と最小公倍数の関係式1

自然数 $a$ と $b$ を素因数分解してみましょう。

$a$ を次のように表します。

$$a = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k}$$

$b$ を次のように表します。

$$b = p_1^{f_1} \times p_2^{f_2} \times \cdots \times p_k^{f_k}$$

ここで、$p_1, p_2, \dots, p_k$ は素数、$e_i$ と $f_i$ はそれぞれの指数です。もしある素数 $p_i$ が片方にしか含まれない場合、その指数は0として考えます。

$a$ と $b$ の最大公約数は、それぞれの素因数の最小の指数で表されます。すなわち、次の式で表されます。

$$\text{gcd}(a, b) = p_1^{\min(e_1, f_1)} \times p_2^{\min(e_2, f_2)} \times \cdots \times p_k^{\min(e_k, f_k)}$$

ここで、$min(e_i,f_i)$は$e_i$と$f_i$のどちらかの小さい値を選択する関数です。

同様に、最小公倍数は、それぞれの素因数の最大の指数で表されます。すなわち、次の式で表されます。

$$\text{lcm}(a, b) = p_1^{\max(e_1, f_1)} \times p_2^{\max(e_2, f_2)} \times \cdots \times p_k^{\max(e_k, f_k)}$$

ここで、$max(e_i,f_i)$は$e_i$と$f_i$のどちらかの大きい値を選択する関数です。

$\text{gcd}(a, b) \times \text{lcm}(a, b)$ の計算をしてみます。

$$\text{gcd}(a, b) \times \text{lcm}(a, b) = \left( p_1^{\min(e_1, f_1)} \times p_2^{\min(e_2, f_2)} \times \cdots \times p_k^{\min(e_k, f_k)} \right) \times \left( p_1^{\max(e_1, f_1)} \times p_2^{\max(e_2, f_2)} \times \cdots \times p_k^{\max(e_k, f_k)} \right)$$

これは、素因数ごとに次のように計算できます。

$$p_1^{\min(e_1, f_1) + \max(e_1, f_1)} \times p_2^{\min(e_2, f_2) + \max(e_2, f_2)} \times \cdots \times p_k^{\min(e_k, f_k) + \max(e_k, f_k)}$$

ここで、次の性質を利用します。

$$\min(e_i, f_i) + \max(e_i, f_i) = e_i + f_i$$

この式の意味は単に、2つの値のうち小さい方と大きい方 をそれぞれ選んで足すと、結局その2つの元の値を足した結果と同じになる、ということです。

したがって、上記の式は次のようになります。

$$p_1^{e_1 + f_1} \times p_2^{e_2 + f_2} \times \cdots \times p_k^{e_k + f_k}$$

これは、 $a \times b$ を素因数分解した形です。したがって、次の関係が成り立ちます。

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

---

例えば、36と48の場合、次のように確認できます。

$$12 \times 144 = 36 \times 48$$

この関係は常に成り立ちます。

3.2. 最大公約数と最小公倍数の関係式2

最大公約数と最小公倍数には、先ほど示したように、次の関係式が成り立ちます。

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

この関係を用いることで、次のように式を変形できます。

$$\begin{align*} \frac{\text{lcm}(a, b) \times \text{gcd}(a, b)}{\text{gcd}(a, b)}& = \frac{a \times b}{\text{gcd}(a, b)} \\ &=\frac{a \times b}{\text{gcd}(a, b)} \\ &=\text{gcd}(a, b)\frac{a \times b}{\text{gcd}(a, b)\times \text{gcd}(a, b)} \end{align*}$$

ここで、$a’ = \frac{a}{\text{gcd}(a,b)}$ および $b’ = \frac{b}{\text{gcd}(a,b)}$ ですから、

$$\text{lcm}(a, b) = \text{gcd}(a, b) \times a’ \times b’$$

4. 例題

次の図のように、まずは公約数で割っていきます。青色で示された部分は、数値同士が互いに素（公約数が1しかない状態）になるまで割り続けます。そして、これ以上公約数で割ることができなくなった段階で、緑色の部分に残った積が最大公約数となります。一方で、この緑色の部分にある積が最大公約数であることに加えて、青色の互いに素である部分の積と掛け合わせると、

$$\text{lcm}(a, b) = \text{gcd}(a, b) \times a’ \times b’$$

になるので、最小公倍数になります。したがって、

$最大公約数=6$

$最小公倍数=6\times 72 = 432$