素数の魅力と素数定理：無限性・一意分解から分布の法則へ

0. この記事の要点

• 素数は「掛け算の原子」です。整数はすべて素数の積に分解でき、しかもその分解は順序を除いて一通りしかありません（算術の基本定理）。この一意性は当たり前ではなく、ベズーの等式を経由した証明を要します。
• 素数は無限個あります。ユークリッドの証明は 2300 年前のものですが、オイラーは $\sum_p 1/p = \infty$ というはるかに強い定量的な形に強化しました。
• $x$ 以下の素数の個数 $\pi(x)$ は $x/\log x$ に漸近します（素数定理）。「$n$ の付近で整数が素数である確率はおよそ $1/\log n$」という直観が、そのまま定理になっています。
• 素数定理そのものは複素解析を要しますが、二項係数 $\binom{2n}{n}$ を眺めるだけで $\pi(x)$ の正しい大きさの上下からの評価（チェビシェフ型）が得られます。この記事ではその評価を完全に証明します。
• 分布の「平均的な姿」は分かっても、個々の素数の振る舞いはほとんど分かっていません。双子素数予想もゴールドバッハ予想も未解決で、誤差項の精密化はリーマン予想そのものです。

1. 動機

素数は、小学校で「1 とその数自身でしか割り切れない数」として習う、数学でもっとも早く出会う概念のひとつです。それにもかかわらず、素数についての基本的な問いのうち相当数が、現在も未解決のまま残っています。この落差こそが数論の出発点です。

歴史をたどると、素数についての最初の定理はユークリッド『原論』第 IX 巻 命題 20 の「素数は与えられたどんな個数よりも多く存在する」です。当時は「無限」という語を避け、有限個の素数のリストが与えられるたびにそこにない素数を作れる、という構成的な形で述べられていました。この形の主張は今読んでも古びていません。

次の大きな一歩は、素数の「個数」ではなく「密度」を問うことでした。ガウスは 15 歳前後（1792–93 年頃）に素数表を眺めていて、$x$ 以下の素数の個数が $\int_2^x dt/\log t$ でよく近似できることに気づきます。同じ頃ルジャンドルは $x/(\log x - 1.08366)$ という近似式を提案しました。どちらも予想であり、証明ではありません。チェビシェフは 1850 年前後に、$\pi(x)$ が $x/\log x$ の定数倍の間に挟まれること、すなわち「正しいオーダー」を初等的な議論だけで確立しました。リーマンは 1859 年の論文で $\pi(x)$ をゼータ関数 $\zeta(s)$ の零点の言葉で書き下す枠組みを与え、それを解析的に完成させたアダマールとド・ラ・ヴァレ・プーサンが 1896 年に独立に素数定理を証明します。ガウスの観察から約 100 年が経っていました。

この記事では、この流れを次の順で追います。まず素数の定義と、整数論のもっとも基本的な道具である除法の原理・ベズーの等式を整備します。次にユークリッドの定理と算術の基本定理を証明します。そのうえで、素数の「多さ」を測る二つの定量的結果（オイラーの発散定理とチェビシェフの評価）を証明し、素数定理を述べ、最後に未解決問題を概観します。証明の技法そのものに不安があれば、証明の技術 - 数学的帰納法と背理法 を先に読んでください。

2. 準備：整除と最大公約数

以下、断りのない限り文字はすべて整数を表します。$\mathbb{N} = \{1, 2, \ldots\}$ とし、$0$ は含めません。

定義 2.1（整除と最大公約数）

整数 $a, b$ について、$b = ac$ を満たす整数 $c$ が存在するとき、$a$ は $b$ を割り切るといい、$a \mid b$ と書きます。割り切らないときは $a \nmid b$ と書きます。

$a, b$ が共に $0$ ではないとき、$a$ と $b$ の最大公約数 $\gcd(a,b)$ を、$a$ と $b$ の共通の約数のうち最大のものと定めます。共通の約数は $\min(|a|,|b|)$ 以下なので、最大値は存在します。$\gcd(a,b) = 1$ のとき $a, b$ は互いに素であるといいます。

定義 2.2（素数と合成数）

$1$ より大きい整数 $p$ が素数であるとは、$p$ の正の約数が $1$ と $p$ だけであることをいいます。$1$ より大きく素数でない整数を合成数といいます。$1$ は素数でも合成数でもありません。

$1$ を素数から除くのは便宜ではなく必然です。$1$ を素数に含めると $6 = 2\cdot 3 = 1 \cdot 2\cdot 3 = 1\cdot 1\cdot 2\cdot 3$ となり、後に述べる素因数分解の一意性が壊れてしまいます。

補題 2.3（除法の原理）

$a$ を整数、$b$ を正の整数とします。このとき

$$a = bq + r, \qquad 0 \le r < b$$

を満たす整数の組 $(q, r)$ がただ一つ存在します。

証明（補題 2.3）

存在。集合 $S = \{a - bq : q \in \mathbb{Z},\ a - bq \ge 0\}$ を考えます。$q = -|a|$ と取ると $a - bq = a + b|a| \ge a + |a| \ge 0$（$b \ge 1$ を使いました）なので $S \ne \varnothing$ です。$S$ は非負整数からなる空でない集合なので、整列性（公理 3.1）［証明の技術］ により最小元 $r = a - bq$ を持ちます。もし $r \ge b$ なら $r - b = a - b(q+1) \ge 0$ も $S$ の元で、$r - b < r$ となり $r$ の最小性に反します。よって $0 \le r < b$ です。

一意性。$bq + r = bq' + r'$（$0 \le r, r' < b$）とすると $b(q - q') = r' - r$ です。$0 \le r, r' < b$ より $|r' - r| < b$ なので $b|q - q'| < b$、すなわち $|q - q'| < 1$ となり $q = q'$、したがって $r = r'$ です。

∎

補題 2.4（ベズーの等式）

$a, b$ を共に $0$ ではない整数とし、$d = \gcd(a, b)$ とします。このとき $d = ax_0 + by_0$ を満たす整数 $x_0, y_0$ が存在します。さらに $d$ は、集合 $I = \{ax + by : x, y \in \mathbb{Z}\}$ に属する正の整数のうち最小のものです。

証明（補題 2.4）

$I$ には $a^2 + b^2 > 0$ が属するので、$I$ に属する正の整数の集合は空ではなく、整列性によりその最小元 $d_0 = ax_0 + by_0$ が存在します。

まず $d_0 \mid a$ を示します。補題 2.3 により $a = d_0 q + r$、$0 \le r < d_0$ と書けます。すると

$$r = a - d_0 q = a - (ax_0 + by_0)q = a(1 - qx_0) + b(-qy_0) \in I$$

です。$0 < r < d_0$ なら $d_0$ の最小性に反するので $r = 0$、すなわち $d_0 \mid a$ です。同様に $d_0 \mid b$ が従うので、$d_0$ は $a, b$ の共通の約数です。

次に、$c$ を $a, b$ の任意の共通の約数とすると、$c \mid ax_0 + by_0 = d_0$ なので $c \le |c| \le d_0$ です。したがって $d_0$ は共通の約数のうち最大であり、定義 2.1 の定義により $d_0 = \gcd(a,b) = d$ となります。

∎

ノート

ベズーの等式は「$\mathbb{Z}$ のイデアルはすべて単項である」という主張の初等的な言い換えです。この視点は 環と体の基礎 で改めて扱います。イデアルの言葉で書き直した主張は 命題 7.2［イデアルと剰余環］ です。

3. 素数の無限性

補題 3.1（最小の約数は素数）

$1$ より大きい任意の整数 $n$ は、少なくとも一つの素因数を持ちます。より正確には、$n$ の $1$ より大きい正の約数のうち最小のものは素数です。

証明（補題 3.1）

$n > 1$ の $1$ より大きい正の約数の集合は $n$ 自身を含むので空ではありません。整列性によりその最小元 $p$ が取れます。$p$ が素数でないとすると、$1 < e < p$ を満たす $p$ の約数 $e$ が存在します。$e \mid p$ かつ $p \mid n$ なので $e \mid n$ であり、$e$ は $n$ の $1$ より大きい約数で $e < p$ です。これは $p$ の最小性に反します。よって $p$ は素数です。

∎

定理 3.2（ユークリッドの定理）

素数は無限に存在します。すなわち、任意の有限個の素数 $p_1, \ldots, p_k$ に対し、そのどれとも異なる素数が存在します。

証明（定理 3.2）

$p_1, \ldots, p_k$ を任意の有限個の素数とし、

$$N = p_1 p_2 \cdots p_k + 1$$

と置きます。各 $p_i \ge 2$ なので $N \ge 3 > 1$ です。補題 3.1 により $N$ は素因数 $q$ を持ちます。

もし $q = p_i$ となる $i$ があったとすると、$q \mid p_1\cdots p_k$ かつ $q \mid N$ なので、その差 $q \mid N - p_1\cdots p_k = 1$ が従います。しかし素数は $2$ 以上なので $q \mid 1$ はあり得ません。よって $q$ は $p_1, \ldots, p_k$ のどれとも異なる素数です。

素数が有限個 $p_1, \ldots, p_k$ しかないと仮定すれば、いま作った $q$ がそのリストに入っていないことになり矛盾します。したがって素数は無限個です。

∎

例 3.3（$p_1\cdots p_k + 1$ は素数とは限らない）

この証明はしばしば「最初の $k$ 個の素数の積に $1$ を足すと新しい素数ができる」と誤って要約されます。実際にはできるのは「新しい素因数を持つ数」であって、その数自身が素数である保証はありません。最初のいくつかは確かに素数です。

$$2+1 = 3,\quad 2\cdot3+1 = 7,\quad 2\cdot3\cdot5+1 = 31,\quad 2\cdot3\cdot5\cdot7+1 = 211,\quad 2\cdot3\cdot5\cdot7\cdot11+1 = 2311$$

はすべて素数です。ところが次の段階で崩れます。

$$2\cdot3\cdot5\cdot7\cdot11\cdot13 + 1 = 30030 + 1 = 30031 = 59 \times 509.$$

実際 $59 \times 509 = 59\times 500 + 59\times 9 = 29500 + 531 = 30031$ です。$30031$ は合成数ですが、その素因数 $59$ と $509$ はどちらも $\{2,3,5,7,11,13\}$ に入っていません。証明が主張しているのはまさにこの点だけです。

4. 算術の基本定理

素数が無限にあることは分かりました。次に、素数が整数全体をどう組み立てているかを見ます。

補題 4.1（ユークリッドの補題）

$p$ を素数、$a, b$ を整数とします。$p \mid ab$ ならば、$p \mid a$ または $p \mid b$ です。

証明（補題 4.1）

$p \mid a$ ならば結論は成り立つので、$p \nmid a$ と仮定して $p \mid b$ を示します。

$\gcd(p, a)$ は $p$ の正の約数なので、定義 2.2 により $1$ か $p$ です。$\gcd(p,a) = p$ なら $p \mid a$ となって仮定に反するので、$\gcd(p, a) = 1$ です。補題 2.4 により

$$1 = px + ay$$

を満たす整数 $x, y$ が存在します。両辺に $b$ を掛けると

$$b = pbx + (ab)y$$

です。右辺の第 1 項は $p$ の倍数であり、第 2 項も仮定 $p \mid ab$ から $p$ の倍数です。よって $p \mid b$ です。

∎

補題の主張は素数に固有です。$p$ が合成数なら成り立ちません。$p = 6$、$a = 2$、$b = 3$ とすると $6 \mid 6 = ab$ ですが $6 \nmid 2$、$6 \nmid 3$ です。

定理 4.2（算術の基本定理）

$1$ より大きい任意の整数 $n$ は素数の積として表せます。さらにその表し方は、因子の順序を除いて一意です。すなわち

$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s$$

（$p_i, q_j$ は素数、$p_1 \le \cdots \le p_r$、$q_1 \le \cdots \le q_s$）ならば $r = s$ かつすべての $i$ について $p_i = q_i$ です。

証明（定理 4.2）

存在。$n$ についての強帰納法（完全帰納法（定理 4.3）［証明の技術］）で示します。$n = 2$ は素数なので $1$ 個の積として表せます。$n > 2$ とし、$2$ 以上 $n-1$ 以下のすべての整数について主張が成り立つと仮定します。$n$ が素数ならそれ自身が求める表示です。$n$ が合成数なら $n = ab$（$1 < a < n$、$1 < b < n$）と書けます。帰納法の仮定より $a$ と $b$ はそれぞれ素数の積で表せるので、それらを並べれば $n$ の素数の積としての表示が得られます。

一意性。$r$ についての帰納法で示します。ここでは「素数を $r$ 個掛けた数として表せる」を $r$ についての主張とみなします。

$r = 1$ のとき。$p_1 = q_1\cdots q_s$ で $p_1$ は素数です。$s \ge 2$ とすると $q_1 \mid p_1$ かつ $1 < q_1 < q_1 q_2 \cdots q_s = p_1$ となり、$p_1$ が素数であること（定義 2.2）に反します。よって $s = 1$ かつ $p_1 = q_1$ です。

$r \ge 2$ とし、$r - 1$ 個の場合に一意性が成り立つと仮定します。$p_1 \mid q_1 q_2\cdots q_s$ なので、補題 4.1 を $s-1$ 回繰り返し適用すると、ある $j$ について $p_1 \mid q_j$ が従います。$q_j$ の正の約数は $1$ と $q_j$ だけで $p_1 > 1$ なので $p_1 = q_j$ です。同じ議論を逆向きに行えば、ある $i$ について $q_1 = p_i$ です。したがって

$$p_1 \le p_i = q_1 \le q_j = p_1$$

となり、$p_1 = q_1$ を得ます（並べ方を昇順にしたことをここで使いました）。両辺を $p_1$ で割ると

$$p_2 \cdots p_r = q_2 \cdots q_s$$

という、左辺が $r-1$ 個の積である等式になります。帰納法の仮定より $r - 1 = s - 1$ かつ $p_i = q_i$（$i \ge 2$）が従い、結論を得ます。

∎

同じ素数をまとめて書けば、$n > 1$ は相異なる素数 $p_1 < \cdots < p_k$ と正の整数 $e_1, \ldots, e_k$ により

$$n = p_1^{e_1} p_2^{e_2}\cdots p_k^{e_k}$$

と一意に書けます。素数 $p$ に対し $p^{e} \mid n$ を満たす最大の $e$ を $v_p(n)$ と書き、$p$ 進付値と呼びます。

例 4.3（$\sqrt{2}$ が無理数であること）

一意分解の典型的な使い方を見ます。$\sqrt 2$ が有理数だとすると $\sqrt 2 = a/b$（$a, b \in \mathbb{N}$）と書けるので $a^2 = 2b^2$ です。両辺に $v_2$ を適用します。$v_2(a^2) = 2v_2(a)$、$v_2(2b^2) = 1 + 2v_2(b)$ なので

$$2v_2(a) = 1 + 2v_2(b)$$

となり、左辺は偶数、右辺は奇数で矛盾します。ここで「両辺の $v_2$ が一致する」と言えるのは、定理 4.2 により分解が一意だからです。一意性を認めなければ、この議論は成立しません。既約分数表示を使う古典的な証明は 定理 7.5［証明の技術］ にあります。

注意 4.4（一意分解は当たり前ではない）

一意性が「当然」に見えるのは、$\mathbb{Z}$ に慣れているせいです。$\mathbb{Z}[\sqrt{-5}] = \{a + b\sqrt{-5} : a, b \in \mathbb{Z}\}$ という環では

$$6 = 2\cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$$

となり、$2, 3, 1\pm\sqrt{-5}$ はいずれもこの環でそれ以上分解できません（ノルム $N(a+b\sqrt{-5}) = a^2 + 5b^2$ を考えると、$N(2) = 4$、$N(3) = 9$、$N(1\pm\sqrt{-5}) = 6$ であり、$N(x) = 2$ や $N(x) = 3$ となる元が存在しないことから分かります）。つまり分解が二通りあります（この例は 例 3.1［フェルマーの最終定理］ でも詳しく扱われます）。$\mathbb{Z}$ で一意性が成り立つ根拠は 補題 2.4、すなわち除法の原理にあり、これは決して一般的な性質ではありません。この破れをどう修復するかがイデアル論の出発点であり、フェルマーの最終定理 の歴史にも直結します。

flowchart TD
A["除法の原理"] --> B["ベズーの等式"]
B --> C["ユークリッドの補題"]
C --> D["算術の基本定理（一意分解）"]
D --> E["オイラー積表示"]
E --> F["Σ 1/p の発散"]
D --> G["二項係数の素因数分解"]
G --> H["チェビシェフ型評価"]
E --> I["素数定理"]
H --> I
I --> J["リーマン予想と誤差項"]

この記事の論理的な骨格。除法の原理から一意分解を経て、素数の分布へ進む

5. 素数はどれくらい多いか

定義 5.1（素数計数関数と漸近同値）

実数 $x$ に対し、$x$ 以下の素数の個数を $\pi(x)$ と書きます。すなわち $\pi(x) = \#\{p : p \text{ は素数},\ p \le x\}$ です。例えば $\pi(10) = 4$（$2,3,5,7$）、$\pi(100) = 25$ です。

また、正値関数 $f, g$ について $\lim_{x\to\infty} f(x)/g(x) = 1$ が成り立つとき $f(x) \sim g(x)$（$x \to \infty$）と書き、$f$ と $g$ は漸近同値であるといいます。

定理 5.2（オイラー：素数の逆数和の発散）

$x \ge 2$ を満たすすべての実数 $x$ について

$$\sum_{p \le x} \frac{1}{p} \ge \log\log x - \frac{1}{2}$$

が成り立ちます（和は $x$ 以下のすべての素数 $p$ にわたります）。特に $\sum_{p} 1/p = \infty$ であり、素数は無限個存在します。

証明（定理 5.2）

第 1 段：調和級数の下からの評価。 $n \le t \le n+1$ のとき $1/n \ge 1/t$ なので $\frac1n \ge \int_n^{n+1}\frac{dt}{t}$ です。$n = 1, \ldots, \lfloor x\rfloor$ について加えると

$$\sum_{n \le x}\frac1n \ \ge\ \int_1^{\lfloor x\rfloor + 1}\frac{dt}{t} \ \ge\ \int_1^{x}\frac{dt}{t} = \log x$$

を得ます（$\lfloor x\rfloor + 1 > x$ を使いました）。

第 2 段：一意分解によるオイラー積の不等式。 $x \ge 2$ を固定し、$x$ 以下の各素数 $p$ について $0 < 1/p \le 1/2 < 1$ なので等比級数

$$\left(1 - \frac1p\right)^{-1} = \sum_{k=0}^{\infty} \frac{1}{p^{k}}$$

が収束します。$x$ 以下の素数は有限個なので、これらを掛け合わせて項別に展開できます。展開して現れる項は $1/(p_1^{k_1}\cdots p_m^{k_m})$ の形で、$p_1, \ldots, p_m$ は $x$ 以下の相異なる素数です。定理 4.2 により、「素因数がすべて $x$ 以下である正の整数 $n$」と、こうした指数の組は一対一に対応します。よって

$$\prod_{p \le x}\left(1 - \frac1p\right)^{-1} = \sum_{n \in A(x)} \frac1n, \qquad A(x) = \{n \in \mathbb{N} : n \text{ のすべての素因数が } x \text{ 以下}\}$$

です。$n \le x$ ならば $n$ の素因数はすべて $n$ 以下、したがって $x$ 以下なので $\{n \in \mathbb{N} : n \le x\} \subset A(x)$ であり、項はすべて正なので第 1 段と合わせて

$$\prod_{p \le x}\left(1 - \frac1p\right)^{-1} \ \ge\ \sum_{n\le x}\frac1n \ \ge\ \log x$$

を得ます。

第 3 段：対数を取って和に直す。 両辺の対数を取ると

$$\sum_{p \le x} \left(-\log\left(1 - \frac1p\right)\right) \ \ge\ \log\log x$$

です。ここで $0 < t < 1$ に対し $-\log(1-t) = \sum_{k\ge1} t^k/k$ なので

$$-\log(1-t) \le t + \frac12\sum_{k \ge 2} t^{k} = t + \frac{t^2}{2(1-t)}$$

が成り立ちます（$k \ge 2$ で $1/k \le 1/2$ を使いました）。$t = 1/p$ とすると

$$-\log\left(1 - \frac1p\right) \le \frac1p + \frac{1}{2p^2}\cdot\frac{p}{p-1} = \frac1p + \frac{1}{2p(p-1)}$$

です。素数についての和を整数についての和で上から抑えると

$$\sum_{p} \frac{1}{2p(p-1)} \le \frac12\sum_{m \ge 2}\frac{1}{m(m-1)} = \frac12\sum_{m\ge2}\left(\frac{1}{m-1} - \frac1m\right) = \frac12$$

です（望遠鏡和）。したがって

$$\log\log x \le \sum_{p\le x}\left(-\log\left(1-\frac1p\right)\right) \le \sum_{p \le x}\frac1p + \frac12$$

となり、移項して主張を得ます。$x \to \infty$ で右辺は $\infty$ に発散するので $\sum_p 1/p = \infty$ です。有限個の素数しかなければ和は有限値なので、素数は無限個です。

∎

この定理は 定理 3.2 より強い情報を持っています。平方数の逆数和 $\sum 1/n^2 = \pi^2/6$ は収束する（バーゼル問題（例 3.5）［リーマン予想とは何か］）ので、「素数は平方数よりも密に分布している」ことが分かるからです。また $\sum_{p\le x} 1/p \approx \log\log x$ という増え方は極端に遅く、素数がかなり薄いことも同時に示しています。

命題 5.3（チェビシェフ型の評価）

$$\liminf_{x\to\infty}\frac{\pi(x)\log x}{x} \ \ge\ \log 2 = 0.6931\ldots, \qquad \limsup_{x\to\infty}\frac{\pi(x)\log x}{x} \ \le\ \log 4 = 1.3862\ldots$$

が成り立ちます。すなわち $\pi(x)$ は $x/\log x$ と定数倍の差しかありません。

証明（命題 5.3）

ここでは下からの評価を証明します。上からの評価は Appendix に回します。

$n$ を正の整数とし、中央二項係数 $C = \binom{2n}{n}$ を考えます。

第 1 段：$C$ は大きい。 二項定理より $\sum_{k=0}^{2n}\binom{2n}{k} = 2^{2n} = 4^n$ です。左辺は $2n+1$ 個の項の和で、$\binom{2n}{n}$ はそのうち最大です（$\binom{2n}{k}$ は $k = n$ で最大値を取ります）。よって

$$(2n+1)\,C \ \ge\ 4^n, \qquad \text{すなわち}\qquad C \ \ge\ \frac{4^n}{2n+1}.$$

第 2 段：$C$ の素因数は小さく、指数も小さい。 $C = (2n)!/(n!)^2$ です。$m!$ に含まれる素数 $p$ の指数は

$$v_p(m!) = \sum_{i \ge 1}\left\lfloor \frac{m}{p^i}\right\rfloor$$

です（$1, \ldots, m$ のうち $p^i$ の倍数はちょうど $\lfloor m/p^i\rfloor$ 個あり、$p$ の指数がちょうど $e$ の数は $i = 1,\ldots,e$ の $e$ 回数えられるため）。したがって

$$v_p(C) = \sum_{i\ge1}\left(\left\lfloor\frac{2n}{p^i}\right\rfloor - 2\left\lfloor\frac{n}{p^i}\right\rfloor\right).$$

実数 $t$ を $t = \lfloor t\rfloor + \theta$（$0 \le \theta < 1$）と書くと $\lfloor 2t\rfloor - 2\lfloor t\rfloor = \lfloor 2\theta\rfloor \in \{0, 1\}$ なので、和の各項は $0$ か $1$ です。さらに $p^i > 2n$ のとき両方の床関数が $0$ になるので項は消えます。よって $v_p(C)$ は $p^i \le 2n$ を満たす $i$ の個数以下であり、

$$p^{v_p(C)} \le 2n$$

が成り立ちます。また $C$ を割り切る素数は $(2n)!$ を割り切るので $p \le 2n$ です。定理 4.2 により $C = \prod_{p \le 2n} p^{v_p(C)}$ と分解できるので、

$$C = \prod_{p\le 2n} p^{v_p(C)} \le (2n)^{\pi(2n)}.$$

第 3 段：両者を突き合わせる。 第 1 段と第 2 段から $(2n)^{\pi(2n)} \ge 4^n/(2n+1)$ です。対数を取ると

$$\pi(2n)\log(2n) \ \ge\ 2n\log 2 - \log(2n+1),$$

すなわち

$$\frac{\pi(2n)\log(2n)}{2n} \ \ge\ \log 2 - \frac{\log(2n+1)}{2n}.$$

$n \to \infty$ のとき右辺は $\log 2$ に収束します。

最後に実数 $x \to \infty$ に移ります。$x \ge 4$ に対し $n = \lfloor x/2\rfloor$ と置くと $2n \le x < 2n + 2$ です。$\pi$ は単調非減少なので $\pi(x) \ge \pi(2n)$ であり、

$$\frac{\pi(x)\log x}{x} \ \ge\ \frac{\pi(2n)\log (2n)}{2n}\cdot\frac{2n}{x} \ \ge\ \left(\log 2 - \frac{\log(2n+1)}{2n}\right)\cdot\frac{x-2}{x}$$

です（$\log x \ge \log 2n$ と $2n > x - 2$ を使いました）。$x\to\infty$ で右辺は $\log 2$ に収束するので、$\liminf$ についての主張を得ます。

∎

6. 素数定理

定義 6.1（対数積分）

$x > 1$ に対し対数積分を

$$\mathrm{li}(x) = \lim_{\varepsilon \to 0+}\left(\int_0^{1-\varepsilon}\frac{dt}{\log t} + \int_{1+\varepsilon}^{x}\frac{dt}{\log t}\right)$$

（$t = 1$ での主値積分）で定めます。部分積分を繰り返すと

$$\mathrm{li}(x) = \frac{x}{\log x} + \frac{x}{(\log x)^2} + \frac{2x}{(\log x)^3} + \cdots$$

という漸近展開が得られ、特に $\mathrm{li}(x) \sim x/\log x$ です。

定理 6.2（素数定理）

$$\pi(x) \sim \frac{x}{\log x} \qquad (x \to \infty),$$

すなわち $\lim_{x\to\infty}\dfrac{\pi(x)\log x}{x} = 1$ が成り立ちます。同値な形として $\pi(x)\sim \mathrm{li}(x)$ も成り立ちます。

注意 6.3（証明について）

素数定理の証明はこの記事の範囲を超えます。1896 年のアダマールとド・ラ・ヴァレ・プーサンによる最初の証明は、リーマンゼータ関数

$$\zeta(s) = \sum_{n=1}^{\infty}\frac{1}{n^{s}} = \prod_{p}\left(1 - \frac{1}{p^{s}}\right)^{-1} \qquad (\operatorname{Re} s > 1)$$

が直線 $\operatorname{Re} s = 1$ 上に零点を持たないことを示す点に核心があります。オイラー積表示（右側の等号、定理 3.1［リーマン予想とは何か］）は 定理 5.2 の第 2 段とまったく同じ論法、つまり 定理 4.2 から従います。素数定理と「$\zeta(1+it)\ne0$」は実は同値であることが知られています。現代的には Newman による短い証明があり、Zagier による 3 ページの解説が読みやすいです。1949 年には Erdős と Selberg が複素解析を使わない初等的証明を与えました（初等的とは「易しい」という意味ではありません）。ゼータ関数の側の話題は リーマン予想とは何か で扱います。

素数定理の意味は「$n$ 付近の整数が素数である確率はおよそ $1/\log n$」という確率的な読み方をすると掴みやすくなります。実際 $\int_2^x dt/\log t$ は、この密度を積分したものにほかなりません。$x = 10^{10}$ 付近では $1/\log(10^{10}) \approx 1/23.0 \approx 4.3\%$ であり、$100$ 個に $4$ 個ほどが素数という計算になります。

数値で確かめます。

$x$	$\pi(x)$	$x/\log x$	$\pi(x)\big/\frac{x}{\log x}$	$\mathrm{li}(x)$	$\mathrm{li}(x)-\pi(x)$
$10^{3}$	168	144.8	1.161	178	10
$10^{4}$	1 229	1 085.7	1.132	1 246	17
$10^{5}$	9 592	8 685.9	1.104	9 630	38
$10^{6}$	78 498	72 382.4	1.084	78 628	130
$10^{7}$	664 579	620 420.7	1.071	664 918	339
$10^{8}$	5 761 455	5 428 681.0	1.061	5 762 209	754
$10^{9}$	50 847 534	48 254 942.4	1.054	50 849 235	1 701
$10^{10}$	455 052 511	434 294 481.9	1.048	455 055 615	3 104

第 4 列は確かに $1$ に向かっていますが、$x = 10^{10}$ でもまだ $4.8\%$ ずれています。これは偶然ではありません。定義 6.1 の漸近展開から $\mathrm{li}(x) - x/\log x \approx x/(\log x)^2$ なので、比の誤差はおよそ $1/\log x$ のオーダーで減ります。$x = 10^{10}$ なら $1/\log x \approx 0.043$ であり、観測された $0.048$ とよく合います。一方、第 6 列の $\mathrm{li}(x)$ との差は $\pi(x)$ 自身に比べて桁違いに小さく、$\mathrm{li}(x)$ がはるかに良い近似であることが読み取れます。

π(x) を x/log x で割った比の推移。1 に近づくものの、その速さは 1/log x でしかない（横軸は x の常用対数）

例 6.4（エラトステネスの篩で $\pi(10^6)$ を数える）

表の値は自分で確かめられます。次のコードは標準ライブラリだけで動きます。

def sieve(n):
    is_prime = bytearray([1]) * (n + 1)
    is_prime[0] = is_prime[1] = 0
    p = 2
    while p * p <= n:
        if is_prime[p]:
            # p*p 未満の p の倍数は、より小さい素因数で既に消えている
            is_prime[p * p :: p] = bytearray(len(range(p * p, n + 1, p)))
        p += 1
    return is_prime


import math

s = sieve(10**6)
pi = sum(s)
print(pi)                       # 78498
print(10**6 / math.log(10**6))  # 72382.41365054197
print(pi / (10**6 / math.log(10**6)))  # 1.0844...

内側の消去を $p^2$ から始めてよいのは、$p^2$ より小さい $p$ の倍数 $kp$（$k < p$）が、$k$ の素因数（補題 3.1）による消去で既に処理されているからです。また外側のループを $p^2 \le n$ で止めてよいのは、$n$ 以下の合成数 $m$ が必ず $\sqrt m \le \sqrt n$ 以下の素因数を持つからです（$m = ab$ で $a \le b$ なら $a \le \sqrt m$、そして $a$ の最小素因数は $a$ 以下）。

例 6.5（素数の空白はいくらでも長い）

素数が平均的に $1/\log n$ の密度で現れるからといって、均等に散らばっているわけではありません。$n \ge 2$ に対し

$$n! + 2,\ n! + 3,\ \ldots,\ n! + n$$

という $n-1$ 個の連続する整数を考えます。$2 \le k \le n$ のとき $k \mid n!$ かつ $k \mid k$ なので $k \mid n! + k$ であり、しかも $1 < k < n! + k$ なので $n!+k$ は合成数です。よって連続する $n-1$ 個の合成数が存在します。$n$ は任意なので、素数の間隔はいくらでも大きくなります。例えば $n = 10$ とすると $3628802, \ldots, 3628810$ の $9$ 個が連続して合成数です（実際にはこの付近にはもっと短い区間で素数が現れますが、存在証明としてはこれで十分です）。

7. 未解決問題

素数定理は「平均としての素数の分布」を完全に決定しました。しかし個々の素数の振る舞いについては、驚くほど何も分かっていません。

7.1. 双子素数予想

差が $2$ の素数の組 $(p, p+2)$ を双子素数といいます。$(3,5), (5,7), (11,13), (17,19), (29,31), \ldots$ と続きます。

双子素数予想：双子素数は無限に存在する。

素数定理から予想される個数のヒューリスティクス（ハーディ–リトルウッドの予想）は、$x$ 以下の双子素数の組の個数が $2C_2 \int_2^x dt/(\log t)^2$（$C_2 = 0.6601\ldots$ は双子素数定数）になるというもので、数値実験とよく合います。しかし無限性すら未解決です。

分かっていることもあります。ブルンは 1919 年に、双子素数の逆数和

$$\left(\frac13+\frac15\right) + \left(\frac15+\frac17\right)+\left(\frac1{11}+\frac1{13}\right)+\cdots$$

が収束することを証明しました（その和はブルン定数と呼ばれ $1.902\ldots$ と推定されています）。定理 5.2 の $\sum_p 1/p = \infty$ と対照的で、双子素数が素数全体よりずっと稀であることを意味します。この収束は、双子素数が有限個であることを意味しない点に注意してください。

2013 年、張益唐は「差が $7\times 10^{7}$ 以下の素数の組が無限に存在する」ことを証明しました。無限性が言えた最初の有限の壁です。直後に Maynard と Tao が独立に別手法を与え、共同研究プロジェクト Polymath を通じて壁は $246$ にまで下げられています。$2$ まで下げるには現在の手法では届きません。

7.2. ゴールドバッハ予想

1742 年にゴールドバッハがオイラーに書いた手紙に端を発します。

（強い）ゴールドバッハ予想：$4$ 以上のすべての偶数は、二つの素数の和として表せる。

$4 = 2+2$、$6 = 3+3$、$8 = 3+5$、$100 = 3+97 = 11+89 = 17+83 = 29+71 = 41+59 = 47+53$ のように、大きな数ほど表し方は増えます。計算機による検証は $4\times 10^{18}$ まで済んでいますが、証明はありません。

弱いゴールドバッハ予想：$7$ 以上のすべての奇数は、三つの素数の和として表せる。

強い予想から弱い予想が従います（奇数 $n \ge 7$ に対し $n - 3$ は $4$ 以上の偶数）。ヴィノグラードフは 1937 年に「十分大きいすべての奇数」について弱い予想を証明し、2013 年に Helfgott が残る有限個の場合を処理して完全な証明を発表しました（正式な出版手続きは長期にわたっています）。強い予想については、陳景潤が 1973 年に「十分大きい偶数は、素数と（素数または二つの素数の積）の和として書ける」ことを示しています。

7.3. 誤差項とリーマン予想

素数定理は $\pi(x) \sim \mathrm{li}(x)$ と述べますが、その誤差 $\pi(x) - \mathrm{li}(x)$ の大きさは決定的な形では分かっていません。フォン・コッホは 1901 年に、リーマン予想が

$$\pi(x) = \mathrm{li}(x) + O\!\left(\sqrt{x}\,\log x\right)$$

と同値であることを示しました（定理 6.3［リーマン予想とは何か］）。上の表で $\mathrm{li}(x)-\pi(x)$ が一貫して正で、しかも $\sqrt x$ 程度の大きさに収まっているのが見て取れます（$x = 10^{10}$ で $\sqrt x = 10^5$、差は $3104$）。

ただし「一貫して正」は永久には続きません。リトルウッドは 1914 年に、$\pi(x) - \mathrm{li}(x)$ が符号を無限回変えることを証明しました。最初に符号が変わる点の位置は現在も特定されておらず、上界（スキューズ数と呼ばれる系列の評価）だけが知られています。計算で見えている範囲がすべてではない、という数論の教訓です。

8. 演習

演習 8.1易

$4n+3$ の形の素数が無限に存在することを証明してください。

解答

$4n+3$ 型の素数が有限個 $p_1 = 3, p_2, \ldots, p_k$ しかないと仮定し、

$$N = 4p_1p_2\cdots p_k - 1$$

と置きます。$N \ge 4\cdot3 - 1 = 11 > 1$ であり、$N \equiv -1 \equiv 3 \pmod 4$ です。

$N$ は奇数なので、その素因数はすべて奇素数、すなわち $4n+1$ 型か $4n+3$ 型です。もし素因数がすべて $4n+1$ 型なら、$(4a+1)(4b+1) = 4(4ab+a+b)+1$ より積も $4n+1$ 型となり、$N \equiv 3 \pmod 4$ に矛盾します。よって $N$ は $4n+3$ 型の素因数 $q$ を持ちます（素因数の存在は 補題 3.1）。

仮定より $q = p_i$ となる $i$ があります。すると $q \mid 4p_1\cdots p_k$ かつ $q \mid N$ なので $q \mid 4p_1\cdots p_k - N = 1$ となり、$q \ge 3$ に矛盾します。したがって $4n+3$ 型の素数は無限個です。

なお $4n+1$ 型の素数の無限性も成り立ちますが、この初等的な議論はそのままでは通用せず、$-1$ が法 $p$ の平方剰余になる条件が必要です。詳しくは 合同式とフェルマーの小定理 を参照してください。

演習 8.2標準

$p_1 = 2 < p_2 = 3 < p_3 = 5 < \cdots$ を小さい順に並べた素数列とします。$\limsup_{n\to\infty}(p_{n+1} - p_n) = \infty$ を示してください。

解答

任意の $M \in \mathbb{N}$ に対し、$p_{n+1} - p_n > M$ を満たす $n$ が存在することを示せば十分です。

$N = (M+1)!$ と置くと、例 6.5 と同じ議論により $N + 2, N+3, \ldots, N + M + 1$ の $M$ 個はすべて合成数です。$N + 1 \ge 3$ なので、$N+1$ 以下の素数の集合は空ではなく有限です。その最大のものを $p_n$ とすると $p_n \le N + 1$ です。

一方 $p_{n+1}$ は $N+1$ より大きい最小の素数ですが、$N+2, \ldots, N+M+1$ はすべて合成数なので $p_{n+1} \ge N + M + 2$ です。よって

$$p_{n+1} - p_n \ge (N + M + 2) - (N+1) = M + 1 > M$$

となります。$M$ は任意なので $\limsup_{n\to\infty}(p_{n+1}-p_n) = \infty$ です。

定理 6.2 は「平均の間隔が $\log p_n$ 程度」であることを示しますが、この演習が示すとおり、個々の間隔はいくらでも大きくなります。

演習 8.3標準

$n$ を正の整数とします。$2^n - 1$ が素数ならば $n$ は素数であることを示してください。また、その逆が成り立たないことを具体例で示してください。

解答

対偶を示します。$n$ が素数でないとします。$n = 1$ のとき $2^1 - 1 = 1$ は素数ではありません。$n$ が合成数のときは $n = ab$（$1 < a < n$、$1 < b < n$）と書けます。恒等式

$$x^{ab} - 1 = (x^{a} - 1)\left(x^{a(b-1)} + x^{a(b-2)} + \cdots + x^{a} + 1\right)$$

に $x = 2$ を代入すると、$2^a - 1$ は $2^n - 1$ を割り切ります。$a > 1$ より $2^a - 1 \ge 3 > 1$ であり、$a < n$ より $2^a - 1 < 2^n - 1$ です。よって $2^n-1$ は $1$ と自分自身以外の約数を持ち、定義 2.2 により素数ではありません。

逆は成り立ちません。$n = 11$ は素数ですが

$$2^{11} - 1 = 2047 = 23 \times 89$$

です（$23 \times 89 = 23\times 90 - 23 = 2070 - 23 = 2047$）。$2^p - 1$ の形の素数はメルセンヌ素数と呼ばれ、無限に存在するかどうかは未解決です。

演習 8.4難

$N$ を $1$ 以上の整数とするとき

$$\pi(N) \ \ge\ \frac{\log N}{2\log 2}$$

が成り立つことを示してください（一意分解だけを使い、二項係数を使わずに素数の無限性の定量版を得る議論です）。

解答

$1 \le n \le N$ を満たす各整数 $n$ を、$n = a b^{2}$（$a$ は平方因子を持たない正の整数、$b$ は正の整数）の形に書きます。実際 定理 4.2 により $n = \prod_p p^{e_p}$ と一意に書けるので、

$$b = \prod_p p^{\lfloor e_p/2\rfloor}, \qquad a = \prod_p p^{e_p - 2\lfloor e_p/2\rfloor}$$

と置けば、$a$ の各指数は $0$ か $1$ なので $a$ は平方因子を持たず、$ab^2 = n$ です。

この $a$ の取り方を数えます。$a$ の素因数は $n \le N$ の素因数なので $N$ 以下であり、各素数が現れるか現れないかの二択なので、$a$ の候補は高々 $2^{\pi(N)}$ 通りです。次に $b$ を数えます。$b^2 \le n \le N$ より $b \le \sqrt N$ なので、$b$ の候補は高々 $\lfloor\sqrt N\rfloor \le \sqrt N$ 通りです。

$n$ から組 $(a,b)$ への対応は単射（$n = ab^2$ から $n$ が復元される）なので、

$$N \ \le\ 2^{\pi(N)}\sqrt{N}$$

を得ます。両辺を $\sqrt N$ で割ると $\sqrt N \le 2^{\pi(N)}$、対数を取って

$$\frac{\log N}{2} \le \pi(N)\log 2, \qquad \text{すなわち}\qquad \pi(N) \ge \frac{\log N}{2\log 2}$$

です。この評価は $\pi(N) \to \infty$ を与えるので素数の無限性を再証明しますが、真の大きさ $N/\log N$ に比べれば圧倒的に弱い評価です。命題 5.3 と比べてみてください。

参考文献

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press, 2008 — 第 1 章（整除と素数）、第 2 章（素数の分布）、第 22 章（素数の分布の続き）。
• 高木貞治『初等整数論講義』第 2 版、共立出版、1971 — 第 1 章（整数の除法、最大公約数、素因数分解）。
• T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976 — 第 3 章（平均の評価）、第 4 章（チェビシェフの関数と素数定理）。
• D. Zagier, “Newman’s short proof of the prime number theorem”, American Mathematical Monthly 104 (1997), 705–708 — 素数定理の解析的証明のもっとも短い現代的な提示。
• Y. Zhang, “Bounded gaps between primes”, Annals of Mathematics 179 (2014), 1121–1174.
• J. Maynard, “Small gaps between primes”, Annals of Mathematics 181 (2015), 383–413.

Appendix: チェビシェフ上界の証明

目標。 命題 5.3 の後半、$\limsup_{x\to\infty}\pi(x)\log x/x \le \log 4$ を証明します。鍵になるのは、素数の個数ではなく素数の対数の和

$$\theta(x) = \sum_{p \le x}\log p$$

（チェビシェフの第一関数）を評価することです。$\theta(x) = \log\left(\prod_{p\le x} p\right)$ なので、以下は「$x$ 以下の素数の積は $4^x$ を超えない」という主張と同じです。

第 1 段：$\prod_{p\le n} p \le 4^{n}$（$n \ge 1$）。 $n$ についての強帰納法で示します。$n = 1$ のとき左辺は空積 $1$、右辺は $4$ で成立します。$n = 2$ のとき左辺は $2$、右辺は $16$ で成立します。

$n \ge 3$ とし、$n$ 未満のすべての正の整数について主張が成り立つとします。$n$ が偶数のとき、$n \ge 3$ より $n$ は素数ではないので $\prod_{p\le n} p = \prod_{p \le n-1} p \le 4^{n-1} \le 4^{n}$ です。

$n$ が奇数のときは $n = 2m+1$（$m \ge 1$）と書きます。$m + 1 < p \le 2m+1$ を満たす素数 $p$ を考えると、$p$ は $(2m+1)!$ の因子として現れる一方、$p > m+1$ より $m!$ も $(m+1)!$ も割り切りません。したがって

$$\binom{2m+1}{m} = \frac{(2m+1)!}{m!\,(m+1)!}$$

は $p$ で割り切れます（補題 4.1 により、分子を割り切る素数が分母を割り切らなければ商に残ります）。相異なる素数についてこれを合わせると（再び 定理 4.2）

$$\prod_{m+1 < p \le 2m+1} p \ \Bigm|\ \binom{2m+1}{m}, \qquad\text{よって}\qquad \prod_{m+1<p\le 2m+1} p \ \le\ \binom{2m+1}{m}.$$

さらに $\binom{2m+1}{m} = \binom{2m+1}{m+1}$ であり、この二つはともに $\sum_{k=0}^{2m+1}\binom{2m+1}{k} = 2^{2m+1}$ の項なので

$$2\binom{2m+1}{m} \le 2^{2m+1}, \qquad \text{すなわち}\qquad \binom{2m+1}{m}\le 4^{m}.$$

帰納法の仮定を $m+1 < n$ に適用すると $\prod_{p \le m+1} p \le 4^{m+1}$ なので、

$$\prod_{p\le 2m+1} p = \left(\prod_{p\le m+1}p\right)\left(\prod_{m+1<p\le 2m+1}p\right) \le 4^{m+1}\cdot 4^{m} = 4^{2m+1} = 4^{n}$$

となり、帰納法が完成します。実数 $x \ge 1$ については $\theta(x) = \theta(\lfloor x\rfloor) \le \lfloor x\rfloor \log 4 \le x\log 4$ です。

第 2 段：$\theta$ から $\pi$ へ。 $1 < y < x$ とします。$y$ より大きく $x$ 以下の各素数 $p$ について $\log p > \log y$ なので

$$\theta(x) \ \ge\ \sum_{y < p \le x}\log p \ >\ (\pi(x) - \pi(y))\log y$$

です。$\pi(y) \le y$ は自明な評価（$y$ 以下の素数は $y$ 以下の正の整数の一部）なので、

$$\pi(x) \ <\ \pi(y) + \frac{\theta(x)}{\log y} \ \le\ y + \frac{x\log 4}{\log y}.$$

第 3 段：$y$ を選ぶ。 $y = x/(\log x)^{2}$ と取ります（$x$ が十分大きければ $1 < y < x$ です）。このとき $\log y = \log x - 2\log\log x$ なので

$$\frac{\pi(x)\log x}{x} \ <\ \frac{1}{\log x} + \frac{\log 4}{1 - \dfrac{2\log\log x}{\log x}}.$$

$x \to \infty$ のとき $\log\log x/\log x \to 0$ なので右辺は $\log 4$ に収束します。したがって $\limsup_{x\to\infty}\pi(x)\log x/x \le \log 4$ です。

まとめ。 命題 5.3 の下界 $\log 2 = 0.693\ldots$ と上界 $\log 4 = 1.386\ldots$ は、定理 6.2 の主張する値 $1$ を実際に挟んでいます。チェビシェフはこの種の議論を精密化して $0.921 < \pi(x)\log x/x < 1.106$（$x$ が十分大きいとき）まで到達しましたが、極限値が $1$ であること自体はこの方向からは出ません。そこにゼータ関数が必要になる、というのが素数定理の物語の核心です。