素数の無限性

同義語:infinitude of primesEuclidの定理(素数)Euclid's theorem

概要

素数の無限性(infinitude of primes)とは、素数が無限に存在するという定理であり、Euclid の定理ともいう。Euclid の証明では、有限個の素数 $p_1,\dots,p_r$ に対して $p_1\cdots p_r+1$ の素因数をとると、それはどの $p_i$ とも異なる(例えば $2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$ は合成数だが、素因数 $59,509$ は新しい素数である)。Euler は素数の逆数の和が発散することを示し、Furstenberg は等差数列を開集合とする整数の位相を使った証明を与えた。一方、$2\cdot3\cdots p+1$ の形の素数が無限にあるかどうかは未解決である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 素数, 約数, 数学的帰納法

動機

素数 $2,3,5,7,11,13,\dots$ は大きくなるにつれてまばらになる。$1$ から $100$ までには $25$ 個あるが、$9{,}901$ から $10{,}000$ までの $100$ 個の整数の中には $9$ 個しかない。いつか素数が尽きてしまうことはないのだろうか。紀元前 300 年ごろに編まれた Euclid の『原論』の答えは「ない」であり、その理由は次の計算に凝縮されている。
$$ 2\cdot3+1=7,\qquad 2\cdot3\cdot5+1=31,\qquad 2\cdot3\cdot5\cdot7+1=211 $$
はどれも素数で、しかも掛けた素数のどれとも異なる。この規則は続かず、$2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$ は合成数であるが、その素因数 $59$ と $509$ はやはり元の $2,3,5,7,11,13$ のどれとも異なる。掛ける素数は最初から順に並べる必要もなく、$\{2,7\}$ なら $2\cdot7+1=15=3\cdot5$ から新しい素数 $3,5$ が、$\{3,5\}$ なら $3\cdot5+1=16=2^4$ から新しい素数 $2$ が得られる。どんな有限個の素数を集めても、それらの積に $1$ を足した数の素因数は、集めた素数のどれとも異なる。こうして素数の表は決して完成しない。
本記事ではこの定理を述べ、Euclid の証明に加えて、Euler による解析的な証明(素数の逆数の和が発散すること)と Furstenberg による位相的な証明を与える。

定理

素数の無限性

素数は無限に存在する。より強く、有限個の素数 $p_1,\dots,p_r$($r\geq0$)をどのように与えても、そのどれとも異なる素数が存在する。

$r=0$(素数を一つも与えない場合)も含めておく。このとき主張は「素数が少なくとも一つ存在する」であり、$2$ がそれである。

証明

Euclidの証明

証明は次の事実だけを使う。$2$ 以上の整数 $N$ の、$1$ より大きい最小の約数は素数である。したがって $2$ 以上の整数は必ず素数で割り切れる(素数 の記事の命題「素因数の存在」。最小の約数 $q$ が $1< c< q$ なる約数 $c$ をもてば、$c$ も $N$ の約数になって最小性に反する)。

積に 1 を足した数の素因数

有限個の素数 $p_1,\dots,p_r$($r\geq0$)を任意にとり、
$$ N:=p_1p_2\cdots p_r+1 $$
とおく。ただし $r=0$ のときは空の積を $1$ と約束して $N=2$ とする。$N\geq2$ なので、$N$ を割り切る素数 $q$ が存在する。$q=p_i$ となる $i$ があるとすると、$q$ は $N$ と $p_1\cdots p_r$ をともに割り切るので、その差 $N-p_1\cdots p_r=1$ を割り切る。しかし $q\geq2$ なので $q\nmid1$ であり、矛盾する。よって $q$ は $p_1,\dots,p_r$ のどれとも異なる素数である。
素数が有限個しかないと仮定すると、それらすべてを $p_1,\dots,p_r$ として上の議論を適用でき、どれとも異なる素数が得られて矛盾する。よって素数は無限に存在する。

この証明は素因数の存在だけを使い、素因数分解の一意性(算術の基本定理)は使わない。前半は背理法ではなく、与えられた有限個の素数から新しい素数を作る手続きになっている。$N$ 自身が素数である必要はない(冒頭の $30031$)。

『原論』における形

『原論』第 IX 巻命題 20 は「素数は、与えられたどんな個数の素数よりも多い」と述べる(Hea08 pp. 412–413)。Euclid は 3 個の素数 $A,B,C$ を代表として、それらすべてで割り切れる最小の数(最小公倍数)に $1$ を足した数を考え、それが素数ならそれが新しい素数、素数でなければ第 VII 巻命題 31(合成数は素数で割り切れる)によりその素因数が新しい素数になる、と場合分けで論じている。素数を無限個の対象の集まりとして扱う現代の言い方ではなく、どんな有限個の素数の組もさらに増やせるという形である。Heath はこの命題の注釈(Hea08 p. 413)で、証明が当時の代数の教科書のものと同じであることを指摘している。

任意の数より大きい素数

任意の整数 $n\geq1$ について、$n< q\leq n!+1$ を満たす素数 $q$ が存在する。ここで $n!$ は階乗である。

階乗に 1 を足す

$N=n!+1\geq2$ を割り切る素数 $q$ をとると $q\leq N$ である。$q\leq n$ なら $q$ は $n!$ の因子なので $q\mid n!$ であり、$q\mid N$ と合わせて $q\mid1$ となり矛盾する。よって $q>n$ である。

4 で割って 3 余る素数

Euclid の議論は、特定の形の素数が無限にあることの証明にも使える。

4 で割って 3 余る素数の無限性

$4$ で割って $3$ 余る素数は無限に存在する。

4 倍して 1 を引く

$q_1,\dots,q_r$($r\geq1$)を $4$ で割って $3$ 余る有限個の素数とし($3$ がその一つなので $r\geq1$ にとれる)、
$$ N:=4q_1q_2\cdots q_r-1 $$
とおく。$N\geq11$ は奇数なので、その素因数はすべて奇素数であり、$4$ で割って $1$ か $3$ 余る。$4$ で割って $1$ 余る数どうしの積は $(4a+1)(4b+1)=4(4ab+a+b)+1$ よりまた $4$ で割って $1$ 余るので、$N$ の素因数がすべて $4$ で割って $1$ 余るなら $N$ も $4$ で割って $1$ 余ることになる。ところが $N=4(q_1\cdots q_r-1)+3$ は $4$ で割って $3$ 余るので、$N$ は $4$ で割って $3$ 余る素因数 $q$ をもつ。$q=q_i$ なら $q$ は $4q_1\cdots q_r-N=1$ を割り切って矛盾する。よって $q$ は $q_1,\dots,q_r$ のどれとも異なる。

たとえば $q_1=3$ から $N=11$、$\{3,11\}$ から $N=131$(素数)が得られる。同じ議論で「$4$ で割って $1$ 余る素数」を扱おうとしても、$4$ で割って $3$ 余る素数 2 個の積は $4$ で割って $1$ 余るので、うまくいかない。$4$ で割って $1$ 余る素数の無限性は、$-1$ が平方剰余になる素数の特徴づけを使って示される(平方剰余 の記事の命題「4 で割って 1 余る素数の無限性」)。一般に、$a$ と $n$ が互いに素なら $n$ で割って $a$ 余る素数は無限に存在する(Dirichletの算術級数定理。主張は HW60 §2.3, Theorem 15, p. 13、Ste17 Theorem 1.2.7, p. 14。この記事では証明しない)が、その証明には Dirichlet指標 と $L$ 関数を使う。$4$ で割って $3$ 余る素数の場合の上の証明は HW60 §2.3, Theorem 11, p. 13 にもある。

Eulerの証明:素数の逆数の和の発散

Euler は、素数の逆数の和 $\frac12+\frac13+\frac15+\frac17+\cdots$ が発散すること(級数)を示した。有限個の正の数の和は有限なので、これは素数が無限にあることを含み、しかも素数が「平方数よりも多い」(平方数の逆数の和 $\sum1/n^2$ は収束する)ことを量的に述べている(Mos11 p. 17。発散は HW60 §2.6, Theorem 19, p. 17 にもある)。以下、$\log$ は自然対数関数、$x\geq2$ は実数とし、$\sum_{p\leq x}$、$\prod_{p\leq x}$ は $x$ 以下の素数 $p$ にわたる和・積を表す。

調和級数の部分和

実数 $x\geq1$ について $\displaystyle\sum_{1\leq n\leq x}\frac1n>\log x$ である。

積分との比較

$m=\lfloor x\rfloor$ とおく。各 $n\geq1$ について、$n\leq t\leq n+1$ で $1/t\leq1/n$ なので $\frac1n\geq\int_n^{n+1}\frac{dt}{t}$ である。$n=1,\dots,m$ について足すと
$$ \sum_{n=1}^{m}\frac1n\geq\int_1^{m+1}\frac{dt}{t}=\log(m+1)>\log x $$
である($m+1>x$)。

Euler積の下からの評価

$x\geq2$ について
$$ \prod_{p\leq x}\Bigl(1-\frac1p\Bigr)^{-1}\geq\sum_{1\leq n\leq x}\frac1n>\log x $$
である。

等比級数の積を展開する

$x$ 以下の素数を $p_1,\dots,p_k$ とする。各 $p_i$ について等比級数の和の公式から $\bigl(1-\frac1{p_i}\bigr)^{-1}=\sum_{e=0}^{\infty}p_i^{-e}$ であり、これは正の項からなる収束級数である。有限個の正項収束級数の積は、各級数から 1 項ずつ選んで掛けたものすべての和に等しい(正項級数なので和の順序を変えてよい)。したがって
$$ \prod_{i=1}^{k}\Bigl(1-\frac1{p_i}\Bigr)^{-1}=\sum_{(e_1,\dots,e_k)}\frac{1}{p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}} $$
である。ここで和は非負整数の組 $(e_1,\dots,e_k)$ すべてにわたる。$1\leq n\leq x$ なる整数 $n$ は、素数の積に分解でき(素数 の記事の定理「算術の基本定理」の存在の部分)、その素因数は $n\leq x$ 以下なので $p_1,\dots,p_k$ のいずれかである。よって $n=p_1^{e_1}\cdots p_k^{e_k}$ となる組があり、$1/n$ は右辺の項として現れる。相異なる $n$ には相異なる組が対応する(組から積 $n$ が決まるので)。右辺の項はすべて正なので、右辺は $\sum_{n\leq x}1/n$ 以上である。後半の不等号は lem-infinitude-of-primes-harmonic である。

素数が有限個しかなければ左辺は $x$ によらず有界であるが、右辺 $\log x$ は $x\to\infty$ で限りなく大きくなるので、これだけで素数の無限性の別証明になる。さらに対数をとると、素数の逆数の和の評価が得られる。

素数の逆数の和の発散

$x\geq2$ について
$$ \sum_{p\leq x}\frac1p>\log\log x-1 $$
である。特に $\sum_p1/p$ は発散し、素数は無限に存在する。

対数の評価

$0< t\leq\frac12$ について
$$ -\log(1-t)=t+\frac{t^2}{2}+\frac{t^3}{3}+\cdots\leq t+\frac{t^2}{2}\bigl(1+t+t^2+\cdots\bigr)=t+\frac{t^2}{2(1-t)}\leq t+t^2 $$
である。prop-infinitude-of-primes-euler-product の両辺の対数をとり、各素数 $p$ に $t=1/p\leq\frac12$ として適用すると
$$ \log\log x<\sum_{p\leq x}-\log\Bigl(1-\frac1p\Bigr)\leq\sum_{p\leq x}\frac1p+\sum_{p\leq x}\frac1{p^2} $$
である。最後の和は
$$ \sum_{p\leq x}\frac1{p^2}\leq\sum_{n=2}^{\infty}\frac1{n^2}<\sum_{n=2}^{\infty}\frac1{n(n-1)}=\sum_{n=2}^{\infty}\Bigl(\frac1{n-1}-\frac1n\Bigr)=1 $$
で押さえられるので、$\sum_{p\leq x}1/p>\log\log x-1$ を得る。$\log\log x\to\infty$($x\to\infty$)なので和は発散する。素数が有限個なら和は有限個の項の和で有界だから、素数は無限に存在する。

より精密な評価と別証明

実際には $\sum_{p\leq x}1/p=\log\log x+O(1)$ であり、上の下界は定数の違いを除いて正しい大きさである(Mos11 Chapter 3, Theorem 4, p. 24)。Moser は $\sum_p1/p$ の発散に、$i\cdot n!-1$($i=1,\dots,m$)の素因数を数える Euclid 型の別証明も与えている(Mos11 pp. 17–18)。ここで述べた Euler の議論は、Riemann ゼータ関数の Euler 積 $\sum_n n^{-s}=\prod_p(1-p^{-s})^{-1}$($s>1$)の $s=1$ での形にあたる(Riemannゼータ関数)。

Furstenbergの位相的証明

H. Furstenberg は、整数全体に位相空間の構造を入れて素数の無限性を示した。$a\in\mathbb{Z}$、整数 $b\geq1$ に対し、等差数列(等差数列と等比数列)
$$ S(a,b):=a+b\mathbb{Z}=\{a+bk\mid k\in\mathbb{Z}\} $$
を考える。

等差数列の位相

$\mathbb{Z}$ の部分集合 $U$ を、「任意の $a\in U$ に対し $S(a,b)\subset U$ となる整数 $b\geq1$ が存在する」ときに開であると定める。

  1. 開な集合の全体は $\mathbb{Z}$ 上の位相(開集合の公理を満たす集合族)である。
  2. 空でない開集合は無限集合である。
  3. 各 $S(a,b)$ は開集合であり、閉集合でもある。
公理の確認

1:空集合は条件を自明に満たし、$\mathbb{Z}$ は $b=1$ で満たす。開集合の族の和集合 $\bigcup_\lambda U_\lambda$ の点 $a$ はある $U_\lambda$ に属するので、$S(a,b)\subset U_\lambda\subset\bigcup_\lambda U_\lambda$ となる $b$ がある。2 つの開集合 $U,V$ の共通部分の点 $a$ について、$S(a,b)\subset U$、$S(a,b')\subset V$ となる $b,b'$ をとると、$S(a,bb')$ は $S(a,b)$ と $S(a,b')$ の両方に含まれるので $S(a,bb')\subset U\cap V$ である。有限個の共通部分も帰納的に開である。
2:空でない開集合 $U$ は点 $a$ とともに無限集合 $S(a,b)$ を含む。
3:$c\in S(a,b)$ なら $S(c,b)=S(a,b)$ なので $S(a,b)$ は開である。また $\mathbb{Z}\setminus S(a,b)=\bigcup_{i=1}^{b-1}S(a+i,b)$ は開集合の和集合なので開であり、$S(a,b)$ は閉集合である。

$\{-1,1\}$ が開集合になる矛盾

$-1,1$ 以外の整数 $m$ は、ある素数 $p$ で割り切れる($m=0$ はすべての素数で、$|m|\geq2$ は $|m|$ の素因数で割り切れる)。したがって
$$ \mathbb{Z}\setminus\{-1,1\}=\bigcup_{p\text{ は素数}}S(0,p) $$
である。素数が有限個しかないと仮定すると、右辺は有限個の閉集合の和集合なので閉集合であり(prop-infinitude-of-primes-furstenberg-topology の 3)、その補集合 $\{-1,1\}$ は開集合になる。しかし $\{-1,1\}$ は空でない有限集合であり、prop-infinitude-of-primes-furstenberg-topology の 2 に反する。よって素数は無限に存在する。

この証明で位相の言葉が担っているのは、「等差数列の有限個の和集合の補集合は、空でなければ無限集合である」という事実である(prop-infinitude-of-primes-furstenberg-topology の 2 と 3)。この事実自体は位相を使わずに確かめられる(有限個の $S(0,p)$ の補集合は、それらの素数の積を $P$ として $S(1,P)$ を含む)。この位相は等差数列位相と呼ばれる。この位相を入れた整数全体の空間が、階乗による超距離で距離化でき、通常の位相の有理数全体と同相になることや、正の素数全体の閉包が正の素数と $\pm1$ からなることなど、空間としての性質は 等差数列位相 で扱う。

帰結と補足

素数の大きさの評価

Euclid の証明は、新しい素数の大きさの上界も与える。$n$ 番目の素数を $p_n$ と書く($p_1=2$、$p_2=3$、$p_3=5$、…)。

素数の大きさの二重指数の上界

すべての $n\geq1$ について $p_n\leq2^{2^{n-1}}$ である。したがって実数 $x\geq2$ について、$x$ 以下の素数の個数 $\pi(x)$ は $\pi(x)>\log_2\log_2x$ を満たす。

強い帰納法

$n=1$ では $p_1=2=2^{2^0}$ である。$n\geq1$ とし、$k\leq n$ で $p_k\leq2^{2^{k-1}}$ が成り立つとする。prf-infinitude-of-primes を $p_1,\dots,p_n$ に適用すると、$N=p_1\cdots p_n+1$ の素因数で $p_1,\dots,p_n$ と異なるものがあり、それは $p_n$ より大きい素数なので $p_{n+1}$ 以上である。よって
$$ p_{n+1}\leq N\leq2^{2^0}\cdot2^{2^1}\cdots2^{2^{n-1}}+1=2^{2^n-1}+1\leq2^{2^n} $$
である($2^0+2^1+\cdots+2^{n-1}=2^n-1$)。
後半:$x\geq2$ に対し $2^{2^{n-1}}\leq x<2^{2^n}$ となる整数 $n\geq1$ をとる。前半により $p_1,\dots,p_n\leq2^{2^{n-1}}\leq x$ なので $\pi(x)\geq n$ である。一方 $x<2^{2^n}$ から $\log_2\log_2x< n$ であり、$\pi(x)>\log_2\log_2x$ を得る。

同じ議論で $\pi(x)\geq\log\log x$($x\geq2$)を示す形が HW60 §2.2, Theorem 10, p. 12 にある。この評価は非常に弱い。$\pi(10^6)=78498$ に対して $\log_2\log_2 10^6$ は $5$ にも満たない。実際の素数の個数は $x/\log x$ 程度であり(素数定理)、また各 $n\geq1$ について $n< p\leq2n$ となる素数が存在するので(Bertrandの仮説)、$p_{n+1}<2p_n$、したがって $p_n\leq2^n$ である。

その他の証明と未解決の問題

その他の証明

素数の無限性には多くの証明が知られている。Fermat 数 $F_m=2^{2^m}+1$ が対ごとに互いに素であることを使う証明(HW60 §2.4, Theorem 16, p. 14。Fermat数 を参照)、$x$ 以下の整数を平方因子と平方因子をもたない部分に分けて個数を数える証明(HW60 §2.6, pp. 16–17。同じ議論で $\sum_p1/p$ の発散も示している)などがある。Moser が「『本物の』数学全体で最もよく知られた証明」と呼ぶように(Mos11 p. 17)、Euclid の証明はその最初のものである。

Euclidの証明が生む未解決問題

Euclid の証明に現れる数 $2\cdot3\cdot5\cdots p+1$($p$ 以下の素数すべての積に $1$ を足した数)や $p!\pm1$ がどのくらいの頻度で素数になるかについては、ほとんど何も分かっていない(Mos11 p. 17)。2026 年の時点でも、$2\cdot3\cdot5\cdots p+1$ の形の素数が無限に存在するかどうかは未解決であり、この形の合成数が無限に存在するかどうかも証明されていない。同様に、差が $2$ の素数の組(双子素数。双子素数予想)が無限に存在するかどうかも未解決である。素数全体の無限性はこのように易しく示せるが、形を指定した素数の無限性は一般に難しい。

反例:条件を外すと成り立たないこと

Euclid の議論と Furstenberg の議論が、どの条件をどこで使っているかを反例で確かめる。

外す条件反例成り立たなくなること
$N$ が単元でないこと($\mathbb Z$ では $N\geq2$)環 $\mathbb Z_{(2)}$ と $N=2+1=3$$N$ の素因数として新しい素元が得られること
和集合が有限個であること$\bigcup_pS(0,p)=\mathbb Z\setminus\{-1,1\}$閉集合の和集合が閉集合であること
剰余類が積で閉じること$4\cdot5+1=21=3\cdot7$$4q+1$ の形から $4$ で割って $1$ 余る新しい素数が得られること
集合が素数全体であること平方数全体 $\{1,4,9,\dots\}$無限集合の逆数の和が発散すること
反例:素元が一つしかない環

分母が奇数の有理数全体 $\mathbb Z_{(2)}=\{a/b\mid a,b\in\mathbb Z,\ b\text{ は奇数}\}$ は、通常の和と積で整域になる。その単元は分子も奇数にとれる元 $a/b$($a,b$ とも奇数)であり、$0$ でない元は $2^k\cdot u$($k\geq0$、$u$ は単元)とただ一通りに書ける。したがって素元は $2$ の単元倍だけで、同伴を除けば素元はただ一つである。この環で Euclid の議論をなぞると、「すべての素元」$2$ の積に $1$ を足した $N=3$ は単元であり、素元で割り切れない。$\mathbb Z$ での証明は「$N\geq2$ なら $N$ は素数で割り切れる」を使っていたが、$\mathbb Z_{(2)}$ ではこれに当たる「$N$ は単元でない」が成り立たない。成り立たないのはこの一段の主張だけで、「$q$ が $p_i$ なら $q\mid1$」の部分はどの環でも正しい。

反例:無限個の閉集合の和集合は閉とは限らない

Furstenberg の位相では各 $S(0,p)$ は閉集合であり、prf-infinitude-of-primes-furstenberg の等式により $\bigcup_pS(0,p)=\mathbb Z\setminus\{-1,1\}$ である。素数は無限にあるので、これは無限個の閉集合の和集合である。その補集合 $\{-1,1\}$ は空でない有限集合なので、prop-infinitude-of-primes-furstenberg-topology の 2 により開集合でない。したがって $\mathbb Z\setminus\{-1,1\}$ は閉集合でなく、無限個の閉集合の和集合は閉集合とは限らない。証明が矛盾を引き出せたのは、素数が有限個だという仮定のもとで「有限個の閉集合の和集合は閉」を使えたからである。

反例:$4$ で割って $1$ 余る素数に Euclid の議論をそのまま使う

$4$ で割って $1$ 余る素数 $5$ に対して $N=4\cdot5+1=21$ とおくと、$N$ は $4$ で割って $1$ 余るが、$21=3\cdot7$ で、素因数 $3,7$ はどちらも $4$ で割って $3$ 余る。prf-infinitude-of-primes-four-three では「$4$ で割って $1$ 余る数どうしの積はまた $4$ で割って $1$ 余る」ことを使って $3$ 余る素因数の存在を導いたが、$4$ で割って $3$ 余る数の積は $3\cdot7\equiv1\pmod 4$ のように $1$ 余る数になるので、逆向きの議論はできない。成り立たないのは剰余類 $3+4\mathbb Z$ が積で閉じるという性質(実際は閉じていない)である。

反例:無限集合でも逆数の和が収束することがある

平方数全体は無限集合だが、prf-infinitude-of-primes-reciprocal の最後の評価と同じく
$$ \sum_{n=1}^\infty\frac1{n^2}<1+\sum_{n=2}^{\infty}\frac1{n(n-1)}=2 $$
で逆数の和は収束する。$2$ の冪 $\{1,2,4,8,\dots\}$ でも逆数の和は $2$ である。したがって「無限に存在する」ことから「逆数の和が発散する」ことは出ず、thm-infinitude-of-primes-reciprocal は素数の無限性より真に強い主張である。素数の逆数の和が発散することは、素数が平方数や $2$ の冪よりずっと多いことを量的に表している。

関連項目

参考文献

[4]
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 4th ed., Oxford, Clarendon Press, 1960, Chapter II:§2.2 Theorem 10(p. 12)、§2.3 Theorem 11・15(p. 13)、§2.4 Theorem 16(p. 14)、§2.6 Theorem 19(pp. 16–17)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する