素数の無限性
解析的証明：素因数分解と対数による $\pi(x)$ の下界評価
問題
素数が無限に存在することを示す。
最も有名な証明はユークリッドの背理法であるが、ここでは素数定理に繋がる解析的なアプローチで証明する。
証明
全ての自然数 $n$ は $p_i$ を $i$ 番目の素数、$k_i$ を $0$ 以上の整数として
$$n = \prod_{i} p_i^{k_i} \tag{1}$$の形に一意に表せる（算術の基本定理。ただし有限個を除き $k_i = 0$）。
この一意性から、$1 \le n \le x$ を満たす自然数 $n$ と、$\prod_i p_i^{k_i} \le x$ を満たす指数の組 $(k_i)$ は1対1に対応する。$1$ から $\lfloor x \rfloor$ までの自然数は $\lfloor x \rfloor$ 個あるから
$$\#\left\{(k_i) \;\middle|\; \prod_i p_i^{k_i} \le x\right\} = \lfloor x \rfloor \tag{2}$$が成り立つ。
次に、条件 $\prod_i p_i^{k_i} \le x$ を満たす組 $(k_i)$ の個数を上から評価する。$\prod_i p_i^{k_i} \le x$ であれば、各因子について
$$p_i^{k_i} \le x \tag{3}$$でなければならない。両辺の $\log$ を取ると
$$k_i \log p_i \le \log x \tag{4}$$より $k_i$ は
$$0 \le k_i \le \dfrac{\log x}{\log p_i} \tag{5}$$を満たす。$k_i$ は $0$ 以上の整数であるから、$k_i$ の取りうる値は $0, 1, 2, \ldots, \left\lfloor \dfrac{\log x}{\log p_i} \right\rfloor$ の $\left\lfloor \dfrac{\log x}{\log p_i} \right\rfloor + 1$ 通り以下である。
ここで、$p_i > x$ なる素数は $k_i = 0$ しか取れない（$p_i^1 > x$ より）ので、$p_i \le x$ すなわち $i = 1, 2, \ldots, \pi(x)$ の範囲だけ考えればよい。ただし $\pi(x)$ は $x$ 以下の素数の個数を表す。
以上より、条件を満たす組の個数は各 $k_i$ の選択肢の積で上から抑えられる：
$$\lfloor x \rfloor \le \prod_{i=1}^{\pi(x)} \left(\left\lfloor \dfrac{\log x}{\log p_i} \right\rfloor + 1\right) \tag{6}$$注意： 左辺が $\lfloor x \rfloor$（式 (2) の等号）で、右辺は各 $k_i$ を独立に動かしたときの組み合わせ数である。条件 $\prod p_i^{k_i} \le x$ を満たす組の集合は、各 $k_i$ を独立に選んだ組の集合に含まれるので、個数について不等号 $\le$ が成り立つ。
$\pi(x)$ は整数値関数であるから、$x$ を正整数に限定しても一般性を失わない。正整数 $x$ に対しては $\lfloor x \rfloor = x$ であり、また $\lfloor \cdot \rfloor$ を外すと右辺は大きくなるだけなので
$$x \le \prod_{i=1}^{\pi(x)} \left(1 + \dfrac{\log x}{\log p_i}\right) \tag{7}$$が成り立つ。
全ての素数は $p_i \ge 2$ を満たすので $\log p_i \ge \log 2$ であり、したがって $\dfrac{\log x}{\log p_i} \le \dfrac{\log x}{\log 2}$ であるから
$$x \le \left(1 + \dfrac{\log x}{\log 2}\right)^{\pi(x)} \tag{8}$$を得る。不等式 (8) の両辺の $\log$ を取ると
$$\log x \le \pi(x) \log\!\left(1 + \dfrac{\log x}{\log 2}\right) \tag{9}$$$\pi(x)$ について解くと
この下界が $x \to \infty$ で発散することを示せば、$\pi(x) \to \infty$ すなわち素数が無限に存在することが証明される。
式 (10) の右辺が発散することの証明
ステップ1：分母を簡単にする
$x \ge 2$ のとき $\dfrac{\log x}{\log 2} \ge 1$ であるから $1 + \dfrac{\log x}{\log 2} \le \dfrac{2\log x}{\log 2}$ が成り立つ。$\log$ は単調増加なので
$$\log\!\left(1 + \dfrac{\log x}{\log 2}\right) \le \log\!\left(\dfrac{2\log x}{\log 2}\right) = \log 2 + \log\log x - \log\log 2 \tag{11}$$$\log\log 2 > 0$ を引いている分だけ右辺は小さくなるので、$-\log\log 2$ を除去すれば右辺は大きくなり、不等号の向きは保たれる：
$$\log\!\left(1 + \dfrac{\log x}{\log 2}\right) \le \log 2 + \log\log x \tag{12}$$式 (10) の分母を式 (12) で置き換えると、分母が大きくなるので $\pi(x)$ の下界は小さくなるが、不等号は保たれる：
$$\pi(x) \ge \dfrac{\log x}{\log 2 + \log\log x} \tag{13}$$
ステップ2：$t = \log x$ とおく
$t = \log x$ とおくと式 (13) は
$$\pi(x) \ge \dfrac{t}{\log 2 + \log t}$$と書ける。十分大きな $x$（具体的には $x \ge e^e$、すなわち $t \ge e > 2$）に対して $\log 2 < \log t$ であるから $\log 2 + \log t \le 2\log t$ となり
$$\pi(x) \ge \dfrac{t}{2\log t} \tag{14}$$
ステップ3：$t/(2\log t) \to \infty$ を示す
$f(t) = \dfrac{t}{2\log t}$ とおく。$f(t)$ を微分すると
$$f'(t) = \dfrac{\log t - 1}{2(\log t)^2}$$となる。$t > e$ のとき $\log t > 1$ であるから $f'(t) > 0$ となり、$f(t)$ は単調増加する。
さらに $f(t) \to \infty$ を示す。$t = e^k\ (k = 1, 2, 3, \ldots)$ とおくと $\log t = \log e^k = k$ であるから、式 (14) は
$$\pi(x) \ge \dfrac{t}{2\log t} = \dfrac{e^k}{2k}$$となる。ここで $\dfrac{e^k}{2k} \to \infty\ (k \to \infty)$ を示す。$e^k$ のテイラー展開
$$e^k = 1 + k + \dfrac{k^2}{2!} + \dfrac{k^3}{3!} + \cdots$$は全ての項が $\ge 0$ であるから、第3項だけ残しても
$$e^k \ge \dfrac{k^2}{2} \tag{15}$$が成り立つ。両辺を $2k > 0$ で割ると
$$\pi(x) \ge \dfrac{e^k}{2k} \ge \dfrac{k^2/2}{2k} = \dfrac{k}{4} \tag{16}$$$k \to \infty$ のとき $\dfrac{k}{4} \to \infty$ であるから、$x = e^k$ の形の点列に沿って $\pi(x) \to \infty$ が示された。$\pi(x)$ は単調非減少であるから、一般の $x \to \infty$ に対しても
$$\pi(x) \to \infty \quad (x \to \infty) \tag{17}$$が成り立つ。すなわち素数は無限に存在する。$\blacksquare$
備考
実際には、素数定理により
$$\pi(x) \sim \dfrac{x}{\log x} \quad (x \to \infty)$$が成り立つことが知られている。これは1792年に15歳のガウスが素数表の観察から予想し、1798年にルジャンドルが独立に公表した。証明は約100年後の1896年にアダマールとド・ラ・ヴァレ＝プーサンによって独立に与えられた。
さらにリーマンは1859年の論文でゼータ関数 $\zeta(s) = \displaystyle\sum_{n=1}^{\infty} n^{-s}$ の零点を用いて $\pi(x)$ の正確な式を導いた：
$$\pi(x) = \operatorname{Li}(x) - \sum_{\rho} \operatorname{Li}(x^{\rho}) - \log 2 + \int_{x}^{\infty} \dfrac{dt}{t(t^2-1)\log t}$$ここで $\operatorname{Li}(x) = \displaystyle\int_2^x \dfrac{dt}{\log t}$ は対数積分、$\displaystyle\sum_{\rho}$ は $\zeta(s)$ の非自明な零点全体にわたる和である。 この等式は素数の分布がゼータ関数の零点に支配されていることを示しており、今なお未解決の「$\zeta(s)$ の非自明な零点の実部は全て $1/2$ か?」というリーマン予想に繋がっている。
なお、本記事の証明はエルデシュの有名な証明の変種である。エルデシュは $x$ 以下の自然数を「平方自由部分 $\times$ 平方数」に分解して $\lfloor x \rfloor \le 2^{\pi(x)}\sqrt{x}$ を得て $\pi(x) \ge \dfrac{1}{2}\log_2 x$ を導いた。本記事では各指数 $k_i$ の範囲を独立に評価して積を取るアプローチ（式 (6)）を取っており、出発点（素因数分解の一意性から組の個数を上から評価する）は共通だが、途中の評価方法が異なる。