約数・倍数・素因数分解【最大公約数・最小公倍数】

整数の性質の学習は、約数・倍数・素因数分解の理解から始まります。これらは高校数学だけでなく、競技数学や情報科学でも重要な概念です。基礎をしっかり固めましょう。

1. 約数と倍数

1.1. 約数（因数）とは

整数 $a$ が整数 $b$ で割り切れるとき、 $b$ を $a$ の約数（または因数）といい、 $a$ を $b$ の倍数といいます。

a \div b \text{ が整数} \Leftrightarrow b \mid a \quad (b \text{ は } a \text{ の約数})

例： 12の約数を求める。

12 ÷ 1 = 12、12 ÷ 2 = 6、12 ÷ 3 = 4、12 ÷ 4 = 3、12 ÷ 6 = 2、12 ÷ 12 = 1

12 \text{ の約数}: 1, 2, 3, 4, 6, 12

1.2. 約数の個数を求める方法

素因数分解を使うと約数の個数が簡単に求まります（後述）。

2. 素数と素因数分解

2.1. 素数とは

1より大きい整数のうち、1とその数自身以外に約数を持たない数を素数といいます。

最初のいくつかの素数： $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots$

1は素数ではありません。

2.2. 素因数分解

任意の自然数は素数の積として一意的に表せます（素因数分解の一意性）。これを素因数分解といいます。

手順： 小さい素数（2, 3, 5, 7, ...）から順に割り算を繰り返します。

360 = 2 \times 180 = 2 \times 2 \times 90 = 2^2 \times 2 \times 45 = 2^3 \times 45

= 2^3 \times 3 \times 15 = 2^3 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5

割り算の筆算（縦書き）：

360 ÷ 2 = 180
180 ÷ 2 = 90
 90 ÷ 2 = 45
 45 ÷ 3 = 15
 15 ÷ 3 = 5
  5 ÷ 5 = 1

360 = 2^3 \times 3^2 \times 5

2.3. 約数の個数の求め方

$n = p^a \times q^b \times r^c \cdots$ （ $p, q, r$ は異なる素数）のとき：

\text{約数の個数} = (a+1)(b+1)(c+1) \cdots

例： $360 = 2^3 \times 3^2 \times 5^1$ の約数の個数

(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24 \text{ 個}

2.4. 例題1：約数の個数

問題： 504の素因数分解を行い、約数の個数を求めよ。

解答：

504 = 2 \times 252 = 2^2 \times 126 = 2^3 \times 63 = 2^3 \times 3^2 \times 7

約数の個数：

(3+1)(2+1)(1+1) = 4 \times 3 \times 2 = 24 \text{ 個}

3. 最大公約数（GCD）

3.1. 最大公約数とは

2つ以上の整数に共通する約数のうち最大のものを最大公約数（GCD, Greatest Common Divisor）といいます。

記号では $\gcd(a, b)$ または $(a, b)$ と書きます。

3.2. 素因数分解を使った GCD の求め方

各数を素因数分解する
共通する素数について、指数の小さい方を選ぶ
積をとる

例： $\gcd(360, 504)$ を求める。

360 = 2^3 \times 3^2 \times 5

504 = 2^3 \times 3^2 \times 7

共通する素数は $2$ と $3$ 。指数の小さい方を選ぶ：

\gcd(360, 504) = 2^3 \times 3^2 = 8 \times 9 = 72

4. 最小公倍数（LCM）

4.1. 最小公倍数とは

2つ以上の整数の公倍数のうち最小の正のものを最小公倍数（LCM, Least Common Multiple）といいます。

記号では $\text{lcm}(a, b)$ または $[a, b]$ と書きます。

4.2. 素因数分解を使った LCM の求め方

各数を素因数分解する
現れるすべての素数について、指数の大きい方を選ぶ
積をとる

例： $\text{lcm}(360, 504)$ を求める。

360 = 2^3 \times 3^2 \times 5^1

504 = 2^3 \times 3^2 \times 7^1

すべての素数の最大指数を選ぶ：

\text{lcm}(360, 504) = 2^3 \times 3^2 \times 5^1 \times 7^1 = 8 \times 9 \times 5 \times 7 = 2520

4.3. GCD と LCM の関係

2数 $a$ 、 $b$ に対して：

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

確認： $72 \times 2520 = 181440 = 360 \times 504$ ✓

この性質を使うと、片方がわかればもう一方が求まります。

4.4. 例題2：GCDとLCMの応用

問題： 2数のGCDが12、LCMが180のとき、2数の積を求めよ。

解答：

\gcd \times \text{lcm} = \text{2数の積}

12 \times 180 = 2160

5. 約数の総和

5.1. 約数の総和の公式

$n = p^a \times q^b$ のとき：

\text{約数の総和} = (1 + p + p^2 + \cdots + p^a)(1 + q + q^2 + \cdots + q^b)

等比数列の和の公式より：

= \frac{p^{a+1}-1}{p-1} \times \frac{q^{b+1}-1}{q-1}

例： $12 = 2^2 \times 3$ の約数の総和

(1 + 2 + 4)(1 + 3) = 7 \times 4 = 28

確認： $1 + 2 + 3 + 4 + 6 + 12 = 28$ ✓

6. まとめ

概念	求め方	ポイント
素因数分解	小さい素数から割り続ける	一意的に決まる
約数の個数	$(a+1)(b+1)\cdots$	各指数に1を加えて掛ける
GCD	共通素数の小さい方の指数	小さい方を選ぶ
LCM	全素数の大きい方の指数	大きい方を選ぶ
GCD × LCM	$= a \times b$	重要な関係式

ユークリッドの互除法でGCDを効率よく求める方法はユークリッドの互除法で解説しています。一次不定方程式は一次不定方程式とn進法で詳しく扱います。

7. クイズ

問1. 84の素因数分解をせよ。また、84の約数の個数を求めよ。

正解： $84 = 2^2 \times 3 \times 7$ 、約数の個数は $(2+1)(1+1)(1+1) = 12$ 個

解説： $84 = 2 \times 42 = 2^2 \times 21 = 2^2 \times 3 \times 7$ 。個数は各指数に1加えて掛ける。

問2. $\gcd(48, 72)$ と $\text{lcm}(48, 72)$ をそれぞれ求めよ。

正解： $\gcd = 24$ 、 $\text{lcm} = 144$

解説： $48 = 2^4 \times 3$ 、 $72 = 2^3 \times 3^2$ 。GCDは $2^3 \times 3 = 24$ 、LCMは $2^4 \times 3^2 = 144$ 。確認： $24 \times 144 = 3456 = 48 \times 72$ ✓

問3. 2数 $a$ 、 $b$ の GCD が 6、 $a = 18$ のとき、 $b$ は何の倍数でなければならないか。

正解： 6の倍数

解説： $\gcd(18, b) = 6$ なので $b$ は 6 の倍数。ただし $b$ が 18 の倍数だと GCD が 18 になる可能性があるため、 $b$ は「6 の倍数かつ 18 の倍数ではない」という条件も加わります（例：6, 12, 24, 30, ...）。