第2章 素数と素因数分解
算術の基本定理
素数とは
定義：素数と合成数
1より大きい自然数 $p$ が素数（prime number）であるとは、$p$ の正の約数が $1$ と $p$ のみであることをいう。
1より大きい自然数で素数でないものを合成数（composite number）という。
注意：$1$ は素数でも合成数でもない（特殊な数として扱う）。
エラトステネスの篩
与えられた範囲内の素数を全て見つける古典的なアルゴリズムがエラトステネスの篩（Sieve of Eratosthenes）である。 紀元前3世紀のギリシャの数学者エラトステネスが考案したとされる。
アルゴリズム：エラトステネスの篩
$N$ 以下の全ての素数を求める手順：
- $2$ から $N$ までの整数のリストを用意する。
- リスト中の最小の未処理の数 $p$ を素数として記録する。
- $p^2, p^2+p, p^2+2p, \ldots$ （$p$ の倍数で $p^2$ 以上のもの）をリストから除去する。
- $p^2 > N$ になるまで手順 2〜3 を繰り返す。
- リストに残った数が全て素数である。
なぜ $p^2$ から始めるのか？ $p$ の倍数のうち $p \cdot k$（$k < p$）はすでにそれ以前の素数 $k$ の段階で除去済みであるから、$p^2$ 未満の倍数を改めて除去する必要はない。
図1. エラトステネスの篩の実行過程（$N = 200$）
以下の図は、$2$ から $200$ までの整数に対してエラトステネスの篩を実行する過程をアニメーションで示す。各段階で素数 $p$ の倍数（$p^2$ 以上）が除去され、最終的に素数だけが残る。$\sqrt{200} \approx 14.1$ なので、$p = 2, 3, 5, 7, 11, 13$ の6ステップで完了する。
素数の無限性
定理（ユークリッド）：素数は無限に存在する
証明（背理法）
素数が有限個しかないと仮定し、すべての素数を $p_1, p_2, \ldots, p_n$ とする。
次の数 $N$ を考える：
$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$$N$ は1より大きいので、ある素数 $p$ で割り切れる。
しかし、$N$ を $p_1$ で割ると $N = p_1 \cdot (p_2 \cdots p_n) + 1$ であるから、余りは必ず $1$ である。同様に $p_2, p_3, \ldots, p_n$ のいずれで割っても余りは $1$ である。
つまり、$N$ はリストに挙げたどの素数でも割り切れない。したがって $N$ を割り切る素数 $p$ は $p_1, p_2, \ldots, p_n$ のいずれとも異なる。
これは「$p_1, \ldots, p_n$ がすべての素数」という仮定に矛盾する。
よって、素数は無限に存在する。$\square$
ユークリッドの補題
次の算術の基本定理を証明するために、まず重要な補題を示す。
補題（ユークリッドの補題）
$p$ が素数で、$p$ が積 $ab$ を割り切るならば、$p$ は $a$ を割り切るか、または $b$ を割り切る。
証明
$p \mid ab$ であるが $p \nmid a$（$p$ は $a$ を割り切らない）と仮定する。$p$ は素数なので、$p$ と $a$ の最大公約数は $\gcd(p, a) = 1$ である（$p$ の約数は $1$ と $p$ しかなく、$p$ は $a$ を割り切らないから）。
$\gcd(p, a) = 1$ であるから、ある整数 $s, t$ が存在して
$$ps + at = 1$$が成り立つ。これはベズーの等式と呼ばれ、ユークリッドの互除法の途中計算を逆にたどることで $s, t$ を具体的に求められる（詳しくはユークリッドの互除法を参照）。両辺に $b$ を掛けると
$$pbs + abt = b$$左辺の第1項 $pbs$ は $p$ で割り切れる。第2項 $abt$ も $p \mid ab$ より $p$ で割り切れる。したがって右辺の $b$ も $p$ で割り切れる。$\square$
算術の基本定理
定理（算術の基本定理）
1より大きい任意の自然数 $n$ は、素数の積として表すことができる。
しかもその表し方は、素因数の順序を除いて一意である。
$$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \quad (p_1 < p_2 < \cdots < p_k, \, e_i \geq 1)$$証明（存在性）
$n > 1$ に対して数学的帰納法で証明する。
$n = 2$ のとき：$2$ は素数なので、それ自身が素因数分解である。
$n - 1$ までの仮定：$2$ 以上 $n-1$ 以下のすべての整数について成り立つと仮定する。
- $n$ が素数なら、$n$ 自身が素因数分解
- $n$ が合成数なら、$n = ab$（$1 < a, b < n$）と書ける
帰納法の仮定より、$a$ と $b$ は素因数分解を持つ。
それらを掛け合わせれば $n$ の素因数分解が得られる。$\square$
証明（一意性）
$n$ に2通りの素因数分解があると仮定する：
$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$$$p_1$ は左辺を割り切るから、右辺 $q_1 q_2 \cdots q_s$ も割り切る。ユークリッドの補題を繰り返し適用すると、$p_1$ はある $q_j$ を割り切る。$q_j$ は素数なので $p_1 = q_j$ である。
両辺から $p_1 = q_j$ を約分して同じ議論を繰り返すと、最終的にすべての素因数が（順序を除いて）一致することが示される。$\square$
素因数分解の応用
約数の個数と総和
$n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ のとき
約数の個数：$\tau(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$
約数の総和：$\sigma(n) = \dfrac{p_1^{e_1+1}-1}{p_1-1} \cdot \dfrac{p_2^{e_2+1}-1}{p_2-1} \cdots \dfrac{p_k^{e_k+1}-1}{p_k-1}$
証明（約数の個数）
$n$ の約数は $d = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ の形をしている（$0 \leq a_i \leq e_i$）。
各 $a_i$ は $0, 1, 2, \ldots, e_i$ の $(e_i + 1)$ 通りの選び方がある。
したがって、約数の個数は $(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)$ 通り。$\square$
証明（約数の総和）
$n$ の約数の総和は、すべての約数 $d = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$（$0 \leq a_i \leq e_i$）の和であるから、
$$\sigma(n) = \sum_{a_1=0}^{e_1} \sum_{a_2=0}^{e_2} \cdots \sum_{a_k=0}^{e_k} p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$各素数 $p_i$ に関する和は独立であるから、この多重和は積に分解できる：
$$= \left(\sum_{a_1=0}^{e_1} p_1^{a_1}\right) \left(\sum_{a_2=0}^{e_2} p_2^{a_2}\right) \cdots \left(\sum_{a_k=0}^{e_k} p_k^{a_k}\right)$$各因子は等比級数の和であるから、
$$\sum_{a=0}^{e} p^a = 1 + p + p^2 + \cdots + p^e = \frac{p^{e+1} - 1}{p - 1}$$したがって、
$$\sigma(n) = \frac{p_1^{e_1+1}-1}{p_1-1} \cdot \frac{p_2^{e_2+1}-1}{p_2-1} \cdots \frac{p_k^{e_k+1}-1}{p_k-1} \qquad \square$$例：$60 = 2^2 \cdot 3 \cdot 5$ の約数
約数の個数：$(2+1)(1+1)(1+1) = 3 \cdot 2 \cdot 2 = 12$ 個
約数の総和：$\dfrac{2^3-1}{2-1} \cdot \dfrac{3^2-1}{3-1} \cdot \dfrac{5^2-1}{5-1} = 7 \cdot 4 \cdot 6 = 168$
約数の列挙：$1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$（和 $= 168$ ✓）
素因数分解による GCD と LCM
2つの自然数 $a, b$ の素因数分解が
$$a = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}, \qquad b = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$$であるとする（共通しない素因数については指数を $0$ とする）。このとき、
最大公約数：$\gcd(a, b) = p_1^{\min(a_1, b_1)} p_2^{\min(a_2, b_2)} \cdots p_k^{\min(a_k, b_k)}$
最小公倍数：$\operatorname{lcm}(a, b) = p_1^{\max(a_1, b_1)} p_2^{\max(a_2, b_2)} \cdots p_k^{\max(a_k, b_k)}$
直感的には、GCD は各素因数について「少ない方の指数」を、LCM は「多い方の指数」を取る。
例：$48$ と $72$ の GCD と LCM
$48 = 2^4 \times 3^1$、$72 = 2^3 \times 3^2$ であるから、
$\gcd(48, 72) = 2^{\min(4,3)} \times 3^{\min(1,2)} = 2^3 \times 3 = 24$
$\operatorname{lcm}(48, 72) = 2^{\max(4,3)} \times 3^{\max(1,2)} = 2^4 \times 3^2 = 144$
検算：$\gcd \times \operatorname{lcm} = 24 \times 144 = 3456 = 48 \times 72$ ✓
暗号への応用
素数と素因数分解は、現代のインターネットセキュリティを支える公開鍵暗号（RSA 暗号など）の基盤となっている。
RSA 暗号の安全性は、次の事実に基づく：
- 2つの大きな素数 $p, q$ の積 $n = pq$ を計算するのは簡単である
- しかし、$n$ だけから $p, q$ を復元する（素因数分解する）のは非常に困難である
この「掛け算は簡単だが逆は困難」という非対称性が、暗号の安全性を保証している。詳しくは以下の記事を参照：
- モジュラ算術 — RSA の数学的基礎
- オイラーのトーシェント関数 — RSA 鍵生成に必要な理論
例題
例題1
$252$ を素因数分解せよ。また、約数の個数を求めよ。
解答
$252 = 2 \times 126 = 2 \times 2 \times 63 = 4 \times 63 = 4 \times 9 \times 7 = 2^2 \times 3^2 \times 7$
約数の個数：$(2+1)(2+1)(1+1) = 3 \times 3 \times 2 = 18$ 個
18 個の約数とその素因数分解を一覧にすると（すべて $2^a \cdot 3^b \cdot 7^c$ の形で統一して書く）：
| 約数 | $a$ | $b$ | $c$ | $2^a \cdot 3^b \cdot 7^c$ |
|---|---|---|---|---|
| $1$ | 0 | 0 | 0 | $2^0 \cdot 3^0 \cdot 7^0$ |
| $2$ | 1 | 0 | 0 | $2^1 \cdot 3^0 \cdot 7^0$ |
| $3$ | 0 | 1 | 0 | $2^0 \cdot 3^1 \cdot 7^0$ |
| $4$ | 2 | 0 | 0 | $2^2 \cdot 3^0 \cdot 7^0$ |
| $6$ | 1 | 1 | 0 | $2^1 \cdot 3^1 \cdot 7^0$ |
| $7$ | 0 | 0 | 1 | $2^0 \cdot 3^0 \cdot 7^1$ |
| $9$ | 0 | 2 | 0 | $2^0 \cdot 3^2 \cdot 7^0$ |
| $12$ | 2 | 1 | 0 | $2^2 \cdot 3^1 \cdot 7^0$ |
| $14$ | 1 | 0 | 1 | $2^1 \cdot 3^0 \cdot 7^1$ |
| $18$ | 1 | 2 | 0 | $2^1 \cdot 3^2 \cdot 7^0$ |
| $21$ | 0 | 1 | 1 | $2^0 \cdot 3^1 \cdot 7^1$ |
| $28$ | 2 | 0 | 1 | $2^2 \cdot 3^0 \cdot 7^1$ |
| $36$ | 2 | 2 | 0 | $2^2 \cdot 3^2 \cdot 7^0$ |
| $42$ | 1 | 1 | 1 | $2^1 \cdot 3^1 \cdot 7^1$ |
| $63$ | 0 | 2 | 1 | $2^0 \cdot 3^2 \cdot 7^1$ |
| $84$ | 2 | 1 | 1 | $2^2 \cdot 3^1 \cdot 7^1$ |
| $126$ | 1 | 2 | 1 | $2^1 \cdot 3^2 \cdot 7^1$ |
| $252$ | 2 | 2 | 1 | $2^2 \cdot 3^2 \cdot 7^1$ |
$a$ は $0, 1, 2$ の 3 通り、$b$ は $0, 1, 2$ の 3 通り、$c$ は $0, 1$ の 2 通りで、$3 \times 3 \times 2 = 18$ 通りの組み合わせがちょうど 18 個の約数に対応している。
例題2
$\gcd(48, 72)$ と $\operatorname{lcm}(48, 72)$ を素因数分解を用いて求めよ。
解答
$48 = 2^4 \times 3$、$72 = 2^3 \times 3^2$ より、
$\gcd(48, 72) = 2^{\min(4,3)} \times 3^{\min(1,2)} = 2^3 \times 3 = 24$
$\operatorname{lcm}(48, 72) = 2^{\max(4,3)} \times 3^{\max(1,2)} = 2^4 \times 3^2 = 144$