素数に最後の 1 個はない〜ユークリッドの論法とエラトステネスのふるい

$100$ 以下の素数は 25 個、$1000$ 以下では 168 個、$10000$ 以下では 1229 個。割合はどんどん薄くなります。

それでも尽きることはありません。素数が有限個だとすると矛盾が出る、という形ではなく、有限個のリストからいつでも新しい素数を作り出せます^[1]。

ユークリッドの論法

素数を好きなだけ並べます。$p_1,p_2,\dots ,p_n$ としましょう。全部を掛けた数に $1$ を足します。

$$N=p_1{p}_2\cdots p_n+1$$

$N$ をリストのどの素数で割っても、余りは $1$ です。積の部分は割り切れ、足した $1$ だけが残るためです。

$N$ は $2$ 以上なので、必ず素因数を持ちます。その素因数はリストのどれとも違う。つまりリストは、いつでも完全ではありません^[2]。

$59$ も $509$ もリストにありません。この操作は何度でもくり返せるので、素数が尽きることはない。

背理法ではない

「素数が有限個だと仮定して矛盾を導く」と説明されることが多いものの、もとの論法は仮定を置いていません^[1]。

与えられた有限個のリストから、そこに入っていない素数を作る。仮定も矛盾も使わない、直接の作り方です。

ユークリッド自身の書き方も「どんな個数の素数を並べても、それより多くの素数がある」という形でした^[2]。

例：小さいリストで試す

$2$ と $3$ から始めます。積に $1$ を足すと $7$ で、これは素数。リストに加えます。

$2,3,5$ なら $31$、$2,3,5,7$ なら $211$。どちらも素数で、そのまま新しい素数になりました。

$2,3,5,7,11$ では $2311$。これも素数です。ここまで 4 回続けて、積に $1$ を足した数が素数になっています。

例：積に 1 を足した数が素数とは限らない

$13$ まで伸ばすと様子が変わります。$2\times 3\times 5\times 7\times 11\times 13=30030$ で、$1$ を足すと $30031$。

$30031=59\times 509$ です。素数ではありません。それでも $59$ と $509$ はリストの外なので、結論は変わらない。

論法が言っているのは「$N$ が素数だ」ではなく「$N$ の素因数がリストの外にある」ということ。ここをとりちがえると、証明が崩れて見えます。

エラトステネスのふるい

素数を実際に数えるには、合成数を消していく方法が使えます^[4]。

$2$ 以上を並べ、$2$ の倍数を消す。次に残った最小の数 $3$ の倍数を消す。これをくり返します。

$100$ 以下では、$2$、$3$、$5$、$7$ の倍数を落とすだけで終わります。残った 25 個が素数です。

平方根まででよい理由

合成数 $n$ は $n=ab$ と書けます。$a$ と $b$ の両方が $\sqrt{n}$ より大きいと、積が $n$ を超えてしまう。

だから小さいほうは必ず $\sqrt{n}$ 以下。$\sqrt{n}$ 以下の素数で落とせば、合成数はすべて消えます^[4]。

$100$ なら $\sqrt{100}=10$ なので、$10$ 以下の素数 $2,3,5,7$ で足りる。$1000$ なら $31$ 以下の 11 個で足ります。

例：1000 以下の素数を数える

$\sqrt{1000}$ はおよそ $31.6$。$31$ 以下の素数は $2,3,5,7,11,13,17,19,23,29,31$ の 11 個です。

この 11 個の倍数を落とすだけで、$1000$ までの合成数がすべて消えます。残るのは 168 個。

$10000$ までなら $\sqrt{10000}=100$ で、$100$ 以下の素数 25 個を使う。残るのは 1229 個です。

割合は薄くなっていく

個数は増え続けますが、密度は下がります。$10$ 以下では 4 個で 4 割、$100$ 以下では 25 個で 4 分の 1。

$10$ 万以下では 9592 個で、割合はおよそ 1 割を切ります。それでも $0$ にはならない。

素数が現れない区間もあります。$113$ の次の素数は $127$ で、あいだの 13 個はすべて合成数です。

別の道：オイラーの証明

素数が有限個なら、素数の逆数を使った無限積が有限の値になります。ところが、それは調和級数と等しい^[1,3]。

調和級数は発散するので、有限の値には収まりません。ここから素数が無限にあると分かります。

ユークリッドの論法より道具は要るものの、素数の分布の細かさまで踏み込める強みがあります。証明は 200 通り以上あると整理されている^[1]。

検算のしかた

ふるいの結果は、区間ごとに数えると確かめやすい。$1$ から $50$ に 15 個、$51$ から $100$ に 10 個で、合わせて 25 個。

小さい素数を落とし忘れていないかも見ます。$91=7\times 13$ は素数に見えやすく、$7$ の段で落ちるはずのものです。

$1$ を素数に数えないことも確かめる。$1$ を含めると素因数分解の一意性が崩れます。

つまずきやすいところ

有限個のリストを渡されたら、掛けて $1$ を足す。それだけで、いつでも外側の素数が 1 つ手に入ります。

参考