§A4.2素数と素因数分解

1 エラトステネスのふるい

$N$以下の素数を一気に列挙する古典的な方法です。

1. $2$から$N$までの整数を並べる。
2. まだ消していない最小の数$p$を素数として確定し、$p$の倍数（$p$自身を除く）をすべて消す。
3. 次に残っている最小の数へ進んで 2 を繰り返す。$p^2 > N$になったら終了。

消し残った数が素数です。$\sqrt{N}$より大きい数についてはふるい落とす必要がないので、$p^2 > N$で打ち切ってよい、というのがこの方法の効率の要です。

2 素因数分解の一意性——算術の基本定理

$2$以上のどの整数も、素数の積として、掛ける順序を除きただ一通りに書けます。これを算術の基本定理と呼びます。$60 = 2^2 \times 3 \times 5$という書き方が他に存在しないことを、私たちは当たり前のように使っていますが、これはまったく自明ではありません。

一意性の証明の核心にあるのはユークリッドの補題です——「素数$p$が積$ab$を割り切るなら、$p$は$a$か$b$の少なくとも一方を割り切る」という主張で、一見当たり前に見えますが、これ自体が証明を要する事実です。この補題は、$\gcd(p, a)$が互除法によって$px + ay = \gcd(p, a)$の形（ベズーの等式）に書けることから導かれます——$p \nmid a$なら$\gcd(p, a) = 1$なので$px + ay = 1$と書け、両辺に$b$を掛けた$pbx + aby = b$の左辺は（$p \mid ab$を使うと）どちらの項も$p$で割り切れるため、右辺の$b$も$p$で割り切れる、という流れです。互除法という計算の道具が、素因数分解の一意性という根本的な事実を裏で支えているわけです。

3 素数は無限に存在する

素数がどこかで尽きてしまわないことも、証明が必要な事実です。ユークリッドによる証明を見てみましょう。

素数は有限個ではありません。 背理法で示します。もし素数が有限個しかなく、それを$p_1, p_2, \dots, p_n$と全部並べられたとします。このとき

$N = p_1 p_2 \cdots p_n + 1$

を考えます。$N$はどの$p_i$で割っても$1$余るので、$p_1, \dots, p_n$のどれによっても割り切れません。ところが$N$は$2$以上の整数なので、素因数を少なくとも1つ持ちます（算術の基本定理より）。その素因数は$p_1, \dots, p_n$のどれとも異なる、新しい素数です。これは「素数は$p_1, \dots, p_n$で全部」という仮定に矛盾します。

ここで「$N$自身が素数である」と誤解しないよう注意してください。証明が言っているのは「$N$の素因数のどれかが$p_1, \dots, p_n$にない新顔だ」ということだけで、$N$自身が素数かどうかは分かりません。実際$2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$は合成数です。