素数が無限個存在することの証明4選 - 気まぐれブログ(日記・技術記事・研究のことなど)

本記事の内容
証明
- 解法1
- 解法2
- 解法3
- 解法4
最後に

本記事の内容

題名の通りです．整数論に関する洋書を輪講で読んでいるのですが，様々な角度から整数論に関することを解説しており，とても面白いです．
その中でも，素数の無限個存在証明をいくつか紹介している部分があり，その部分をまとめてみました．

Concrete Mathematics: A Foundation for Computer Science

作者:Graham, Ronald L. Knuth, Donald E. Patashnik, Oren
発売日: 1994/02/28
メディア: ハードカバー

証明

解法1

証明
素数が $k$ 個( $p_1, p_2, ..., p_k$ )のみ存在すると仮定する．
$M = p_1p_2...p_k + 1$ はどの $p_i (1 \leq i \leq k)$ でも割り切れないので， $M$ は素数．
これは素数が $k$ 個のみ存在することに矛盾する．

解説
一番ベーシックな解法．高校生で一度は触れる(はず？)．

解法2

証明
$e_n = e_1e_2...e_{n-1} + 1$ とする．ただし $e_1 = 2$ である．
任意の $m, n (m \neq n)$ において，gcd( $e_m, e_n$ ) = 1が成立する．
$q_j$ を $e_j$ における最小の素因数とすると， $q_1, q_2, q_3, ...$ はそれぞれ値の異なる無限の素数列となる．
したがって素数は無限個存在する．

解説
$e_n$ (これをユークリッド数という)の性質をうまく利用した，美しい解法．

解法3

証明
$x$ を素因数分解したとき，素因数 $p$ の指数部の値を $\epsilon_p(x)$ と書くことにする．
例えば， $18 = 2^1 \cdot 3^2$ より， $\epsilon_2(18) = 1$ , $\epsilon_3(18) = 2$ ．

まず， $p^{\epsilon_p(n!)} < 2^n$ を証明する．

$\epsilon_p(n!)$ の値を考えると， $\epsilon_p(n!) = \lfloor \frac{n}{p} \rfloor + \lfloor \frac{n}{p^2} \rfloor + ... = \sum_{k \geq 1} \lfloor \frac{n}{p^k} \rfloor$ と書ける．

上記事実から， $\epsilon_p(n!) < \frac{n}{p} + \frac{n}{p^2} + ... = \frac{n}{p-1}$ が成立(無限等比級数の和の公式を使用)．
したがって， $p^{\epsilon_p(n!)} < p^{n/(p-1)} \leq (2^{p-1})^{n/(p-1)} \leq 2^n$ が成立(途中， $p \leq 2^{p-1}$ の関係式を利用)．

続いて， $n^{n/2} \leq n! \leq (n+1)^n/2^n$ を証明する．

まず $n!^2 = (1\cdot 2\cdot ... \cdot n)(n \cdot ... \cdot 2 \cdot 1) = \prod_{k=1}^n k(n+1-k)$ が成立．
ここで関係式 $n \leq k(n+1-k) \leq (n+1)^2/4$ を使用すると，
$\prod_{k=1}^nn \leq n!^2 \leq \prod_{k=1}^n (n+1)^2/4$ が成立．
したがって， $n^{n/2} \leq n! \leq (n+1)^n/2^n$ が成立．

ここで解法1と同様に，素数が $k$ 個のみ存在すると仮定すると，
$n! < (2^n)^k = 2^{nk}$ が成立する．
ここで $n = 2^{2k}$ とおくと， $n! < 2^{nk} = 2^{2^{2k}k} = n^{n/2}$ が成立する．
しかし，これは $n^{n/2} \leq n! \leq (n+1)^n/2^n$ という関係式に矛盾する．

したがって素数は無限個存在する．

解説
$n!$ に関する性質をうまく利用して，背理法で証明．

解法4

証明
$n$ 以下に存在する素数の個数を $\pi(n)$ で表すとする．
解法3と同じ考え方で， $n! < 2^{n\pi(n)}$ が成立する．
ここでスターリングの公式( $n! \approx \sqrt{2\pi n} (n/e)^n$ )を利用して，式変形すると，
$n\pi(n) > n\log(n/e) + (1/2)\log(2\pi n)$ となる．したがって，
$\pi(n) > \log(n/e)$ が成立する．
$n \to \infty$ のとき，右辺が $\infty$ であることから， $\pi(n)$ も $\infty$ となる．
よって素数は無限個存在する．