基礎知識

ここでは基本的な最大公約数と最小公倍数の求め方についてと、少し応用的な問題を、例題を通じて説明していきます。

最大公約数とは？最小公倍数とは？

複数の正の整数について、共通する約数のうち最大のものを最大公約数、共通する倍数のうち最小のものを最大公約数といいます。

最大公約数と最小公倍数を求め方

例題を通じて、最大公約数と最小公倍数を求め方を理解していきましょう。

例題

解答

$$\begin{array}{rcl} 3780 &=& 2^2 \cdot 3^3 \cdot 5^1 \cdot 7^1 \\\\ 360 &=& 2^3 \cdot 3^2 \cdot 5^1 \\\\ \end{array}$$

最大公約数は

$$\begin{array}{rcl} 2^2 \cdot 3^2 \cdot 5^1 &=& 4 \cdot 9 \cdot 5 \\\\ &=& 180 \\\\ \end{array}$$

最小公倍数は

$$\begin{array}{rcl} 2^3 \cdot 3^3 \cdot 5^1 \cdot 7^1 &=& 8 \cdot 27 \cdot 5 \cdot 7 \\\\ &=& 7560 \\\\ \end{array}$$

応用問題

例題

解答

求める $2$ つの数を $a, b ~(a < b)$ とおき、最大公約数が $180$ であることから、

$$\begin{array}{rcl} a &=& 180a’ \\\\ b &=& 180b’ \\\\ \end{array}$$

（ただし、 $a’, b’ ~(a’ < b’)$ は互いに素な自然数）

【整数】互いに素とは

と表せます。

また、最小公倍数が $7560$ であることから、

$$\begin{array}{rcl} 7560 &=& 180a’b’ \\\\ \end{array}$$

上式を約分すると、

$$\begin{array}{rcl} 42 &=& a’b’ \\\\ \end{array}$$

となります。
$a’, b’$ は互いに素な自然数なので、積が $42$ となる $(a’, b’)$ の組み合わせを全て書き出すと次のようになります。

$$\begin{array}{rcl} (a’, b’) = (1, 42), (2, 21), (3, 14), \\\\ (6, 7), (7, 6), (14, 3), (21, 2), (42, 1) \end{array}$$

これらのうち、 $a’ < b’$ を満たすのは

$$\begin{array}{rcl} (a’, b’) = (1, 42), (2, 21), (3, 14), (6, 7) \end{array}$$

となるので、

$$\begin{array}{rcl} (a, b) = (180, 7560), (360, 3780) ,\\\\ (540, 2520), (1080, 1260) \end{array}$$

以上により、最大公約数が $180$ 、最小公倍数が $7560$ である $2$ 数は

$$\begin{array}{rcl} (180, 7560), (360, 3780) , \\\\(540, 2520), (1080, 1260) \end{array}$$

となります。

最大公約数と最小公倍数の説明のおわりに

いかがでしたか？

ここで紹介した応用問題にあるように、最大公約数や最小公倍数を方程式として扱えるようになることが大切です。

また、「互いに素」は、整数問題について特に重要な概念ですので、しっかり理解しておくようにしましょう。

【基礎】整数の性質のまとめ