素数はなぜ「原子」なのか ― 算術の基本定理が言っていること
素因数分解の一意性は「当然」ではありません．Z[√-5] での反例を通じて一意性の崩壊を実感し，算術の基本定理の存在証明と一意性証明，エラトステネスの篩と線形篩を解説します．
「任意の正整数は素因数分解でき，その分解は一意である」― これは算術の基本定理と呼ばれ，整数論の土台です．しかし，この「当然」に見える事実は，実は深い構造的理由があって成り立っています．別の数の世界では一意性が崩壊するからです．
1 素数の定義
定義 1 (素数).
以上の整数 が素数であるとは， の正の約数が と のみであることです．素数でない 以上の整数を合成数と呼びます．
注意 2.
素数は整数の「原子」です．化学で分子が原子に分解されるように，整数は素数の積に分解されます．しかし化学の原子と違い，素数は無限に存在します．
定理 3 (素数の無限性（ユークリッド）).
素数は無限に存在します．
証明.
素数が有限個 しかないと仮定します． を考えると， はどの でも割り切れません（割ると余り ）．しかし なので素因数をもちます．これは仮定に矛盾します． □
2 算術の基本定理 ― 存在の証明
定理 4 (算術の基本定理).
任意の 以上の整数 は，素数の積として
と表され，この表示は（順序を除いて）一意です．
存在と一意性を分けて証明します．
証明.
に関する強帰納法を用います． なら素数なので成り立ちます． とします． が素数ならそれ自身が素因数分解です． が合成数なら （）と書け，帰納法の仮定により はそれぞれ素因数分解をもつので，それらの積が の素因数分解です． □
3 一意性の証明 ― ここが本質
一意性の証明には，次の補題が鍵です．
定理 5 (ユークリッドの補題).
が素数で ならば， または ．
証明.
とします． は素数なので ．ベズーの等式より となる整数 が存在します．両辺に をかけると ． より ，また なので ． □
注意 6.
ユークリッドの補題はベズーの等式，したがってユークリッドの互除法に依拠しています．前回の記事で証明した結果が，ここで本質的に使われるのです．
証明.
とします． です．ユークリッドの補題を繰り返し適用すると，ある で ． は素数なので ．両辺を で割り，帰納法を適用すれば一意性が従います． □
4 一意性が崩壊する世界 ―の反例
一意性は「当然」ではありません．次の例を見てください．
例 7 ( での一意性の崩壊).
を考えます．この世界で を「素因数分解」すると，
となり，2通りの分解が存在します．
注意 8.
はいずれも で「既約」（これ以上分解できない）です．これはノルム を使って確認できます：，，．ノルムが積に対して をみたすので，もし と分解できるなら です． や をとる元は存在しない（ の整数解がない）ので， は既約です．
注意 9.
でユークリッドの補題が成り立たないことが根本原因です． ですが， かつ です．ユークリッドの互除法が使えない環では，補題が崩壊し，一意性も崩壊するのです．
5 エラトステネスの篩
素数を具体的に列挙する古典的アルゴリズムです．
定理 10 (エラトステネスの篩).
から までの素数を 時間で列挙できます．
注意 11.
アルゴリズムは単純です： から順に，まだ消されていない数を見つけたらそれは素数．その素数の倍数をすべて消します． まで処理すれば十分です（ 以下の合成数は 以下の素因数をもつ）．計算量は （メルテンスの定理）より です．
6 線形篩 ― 各合成数を1回だけ消す
注意 12 (線形篩).
エラトステネスの篩では，合成数が複数回消される無駄があります（例： は の倍数としても の倍数としても消される）．線形篩は，各合成数をその最小素因数でちょうど1回だけ消すことで， 時間を実現します．各数の最小素因数も同時に求まるので， での素因数分解にも使えます．
7 まとめ
素数は整数の「原子」であり，無限に存在します
算術の基本定理は，素因数分解の存在と一意性を主張します
一意性はユークリッドの補題（したがってベズーの等式）に依拠しています
ではユークリッドの補題が成り立たず，一意性が崩壊します
エラトステネスの篩は ，線形篩は で素数を列挙します
次の記事では，素数の世界における「対称性」― フェルマーの小定理に迫ります．