素数
概要
素数（prime number）とは、$2$ 以上の整数で、正の約数が $1$ と自分自身だけであるもののことである。$2,3,5,7,11,\dots$ と無限に続き（Euclid の証明）、$2$ 以上のすべての整数は素数の積としてただ 1 通りに書ける（算術の基本定理）。一意性の鍵は、素数 $p$ が $ab$ を割り切れば $a$ か $b$ を割り切るという Euclid の補題で、Bézout の等式から従う。$1$ は素数に含めない。含めると分解の一意性が崩れ、環論的には $1$ が単元だからである。$x$ 以下の素数の個数 $\pi(x)$ は $x/\log x$ に漸近する（素数定理）。環論では素数は整数環の素元、$(p)$ は素イデアルであり、$\mathbb{Z}/p\mathbb{Z}$ は体になる。
前提知識: 整数, 約数, Bézoutの等式
素数とは、$1$ より大きい整数で、$1$ と自分自身のほかに正の約数をもたないもののことである。$2,3,5,7,11,\dots$ と続く。$1$ より大きいすべての整数は素数の積に分解でき、その分解は積の順序を除いてただ 1 通りである（素因数分解の存在と一意性）。この意味で素数は整数の乗法の「原子」であり、整数論の多くの問題は素数についての問題に帰着される。一意性の鍵は、素数 $p$ が積 $ab$ を割り切るなら $a$ か $b$ を割り切るという性質（Euclid の補題）であり、これはBézoutの等式から従う。
定義
整数 $p$ が 素数（prime number）であるとは、$p\geq2$ であり、$p$ の正の約数が $1$ と $p$ だけであることをいう。
整数 $n\geq2$ が素数でないとき、$n$ は 合成数（composite number）であるという。
$n\geq2$ が合成数であることは、$1< d< n$ を満たす約数 $d$ をもつこと、すなわち $n=ab$、$1< a< n$、$1< b< n$ と書けることと同値である（$d$ が約数なら $n=d\cdot(n/d)$ で $1< n/d< n$ である）。したがって、$2$ 以上の整数は素数と合成数のちょうど一方であり、$0$、$1$、負の整数はどちらでもない。
$1$ の正の約数は $1$ だけなので、「正の約数が $1$ と自分自身だけ」という条件は $1$ についても成り立つ。それでも定義で $p\geq2$ を要求して $1$ を除くのは、次の理由による。
- $1$ を素数に含めると、素因数分解の一意性（thm-prime-number-fta）が成り立たない。$6=2\cdot3=1\cdot2\cdot3=1\cdot1\cdot2\cdot3$ のように、$1$ をいくつでも掛け加えた表示ができるからである。
- $1$ は掛け算の単位元であり、環 $\mathbb{Z}$ の単元である。環論では単元を素元・既約元から除く（素元、既約元）。$\mathbb{Z}$ の素元は $\pm p$（$p$ は素数）であり、単元 $\pm1$ は含まれない。
- 素イデアルは真のイデアルとして定義されるので、$(1)=\mathbb{Z}$ は素イデアルでない。剰余環 $\mathbb{Z}/1\mathbb{Z}$ は零環であり、体でも整域でもない。素数 $p$ に対しては $\mathbb{Z}/p\mathbb{Z}$ が体になる（rem-prime-number-ideal）。
本記事では素数は正の整数とし、負の整数 $-p$ は素数と呼ばない。環 $\mathbb{Z}$ の素元としては $p$ と $-p$ が同じ役割を果たす。
直感
整数を掛け算で分解していくと、それ以上分解できない数に行き着く。$60=6\cdot10=(2\cdot3)\cdot(2\cdot5)$ の $2,3,5$ がそれである。素数はこの「それ以上分解できない」数であり、すべての整数は素数を部品として組み立てられる。部品の選び方がただ 1 通りであることは自明ではなく、掛け算だけを見ていても証明できない。$4$ で割って $1$ 余る正の整数だけからなる世界では、分解の一意性が崩れる（ex-prime-number-one-mod-four）。整数で一意性が成り立つのは、足し算と掛け算を組み合わせた Bézout の等式 $px+ay=1$ が使えるからである。
素数はどこまでも現れる（thm-prime-number-infinite）が、大きくなるにつれてまばらになる。$x$ 以下の素数の個数はおよそ $x/\log x$ であり（素数定理）、$x$ の近くの整数が素数である「確率」はおよそ $1/\log x$ である。
例と反例
$50$ 以下の素数は
$$
2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37,\ 41,\ 43,\ 47
$$
の 15 個である。$2$ は偶数である唯一の素数である。実際、$n>2$ が偶数なら $2$ は $1<2< n$ を満たす約数なので $n$ は合成数である。したがって $3$ 以上の素数はすべて奇数である。
$1$ より大きい奇数であっても素数とは限らない。$9=3\cdot3$、$15=3\cdot5$、$91=7\cdot13$ は合成数である。$91$ は $2,3,5$ のいずれでも割り切れないが、$7$ で割り切れる。
合成数の判定は、小さい素因数を探せば足りる。$n$ が合成数なら $\sqrt n$ 以下の素因数をもつ（prop-prime-number-factor の 2）ので、$91$ については $\sqrt{91}<10$ より $2,3,5,7$ を調べれば十分である。この原理に基づいて、$2$ から順に素数の倍数を消していき素数表を作る方法を Eratosthenesの篩 という。
特定の形の数がつねに素数になるとは限らない。
- $n^2+n+41$ は $n=0,1,\dots,39$ ではすべて素数であるが、$n=40$ では $40^2+40+41=1681=41^2$ で合成数である。「最初の 40 個が素数なら以後も素数」という推論は成り立たない。
- $2^{2^m}+1$ の形の数を Fermat 数（Fermat数）という。$m=0,1,2,3,4$ に対する $3,5,17,257,65537$ は素数であるが、$m=5$ では $2^{32}+1=4294967297=641\cdot6700417$ で合成数である（HW08 Chapter II）。
- $2^m-1$ が素数なら $m$ は素数である（$m=ab$、$a,b>1$ なら $2^a-1$ が $2^m-1$ の $1<2^a-1<2^m-1$ を満たす約数になる）。しかし逆は成り立たない。$m=11$ は素数だが $2^{11}-1=2047=23\cdot89$ である。素数になる $2^m-1$ を Mersenne素数 という。
- Euclid の証明（thm-prime-number-infinite）に現れる $p_1\cdots p_r+1$ も素数とは限らない。$2\cdot3\cdot5\cdot7\cdot11\cdot13+1=30031=59\cdot509$ である。
$4$ で割って $1$ 余る正の整数全体 $H=\{1,5,9,13,17,21,\dots\}$ は掛け算で閉じている（$(4a+1)(4b+1)=4(4ab+a+b)+1$）。$H$ の元 $h>1$ で、$H$ の元 $h_1,h_2>1$ の積 $h=h_1h_2$ に書けないものを「$H$ の素数」と呼ぶことにする。
$9$、$21$、$49$ は $H$ の素数である。たとえば $21=3\cdot7$ の 1 より大きい約数は $3,7,21$ であり、$3$ と $7$ は $H$ に属さないので、$21$ は $H$ の 2 元の積に書けない。$9=3\cdot3$、$49=7\cdot7$ も同様である。ところが
$$
441=9\cdot49=21\cdot21
$$
であり、$441$ は $H$ の素数の積として 2 通りに書ける。$H$ の素数 $21$ は $9\cdot49$ を割り切るが、$9$ も $49$ も割り切らない（$H$ の中の割り算で）。この例は、「それ以上分解できない」ことだけからは Euclid の補題（lem-prime-number-euclid）も一意性も導けないことを示している。$H$ は足し算で閉じていないので、Bézout の等式を使う議論ができない。
性質
素因数の存在と素数の無限性
$n\geq2$ を整数とする。
- $n$ の約数のうち $1$ より大きい最小のもの $p$ は素数である。特に $n$ は素数で割り切れる。
- $n$ が合成数なら、1 の $p$ は $p\leq\sqrt n$ を満たす。
- $n$ 自身が $1$ より大きい約数なので、$1$ より大きい正の約数の集合は空でなく、最小元 $p$ がある。$p$ が合成数なら $1< c< p$ を満たす $p$ の約数 $c$ があり、$c\mid p$、$p\mid n$ から $c\mid n$ となって $p$ の最小性に反する。よって $p$ は素数である。
- $n$ が合成数なら $n=ab$、$1< a\leq b< n$ と書ける。$a$ は $1$ より大きい約数なので $p\leq a$ であり、$a^2\leq ab=n$ から $p\leq a\leq\sqrt n$ である。
$p_1,\dots,p_r$（$r\geq1$）を有限個の素数とすると、そのどれとも異なる素数が存在する。したがって素数は無限に存在する。
$N:=p_1p_2\cdots p_r+1$ とおく。$N\geq3$ なので、prop-prime-number-factor により $N$ はある素数 $q$ で割り切れる。$q=p_i$ となる $i$ があるとすると、$q$ は $N$ と $p_1\cdots p_r$ をともに割り切るので、その差 $1$ を割り切り、$q\geq2$ に反する。よって $q$ は $p_1,\dots,p_r$ のどれとも異なる素数である。
素数が有限個しかないとすると、$2$ は素数なのでそれらは $r\geq1$ 個の素数 $p_1,\dots,p_r$ として並べられるが、前半によりそれ以外の素数があって矛盾する。
この証明は Euclid の『原論』にさかのぼる（HW08 Chapter II）。証明が使うのは素因数の存在だけであり、素因数分解の一意性は使わない。
Euclidの補題
$p$ を素数、$a,b$ を整数とする。$p\mid ab$ ならば $p\mid a$ または $p\mid b$ である。
逆に、整数 $p\geq2$ が「任意の整数 $a,b$ について $p\mid ab$ ならば $p\mid a$ または $p\mid b$」を満たすならば、$p$ は素数である。
$p\mid ab$ かつ $p\nmid a$ と仮定して $p\mid b$ を示す。最大公約数 $\gcd(p,a)$ は $p$ の正の約数なので $1$ か $p$ であり、$p\nmid a$ より $p$ ではない。よって $\gcd(p,a)=1$ であり、Bézoutの等式により $px+ay=1$ となる整数 $x,y$ がある。両辺に $b$ を掛けると
$$
b=p(bx)+(ab)y
$$
であり、右辺の 2 項はともに $p$ で割り切れる（後者は $p\mid ab$ による）。よって $p\mid b$ である。
逆を示す。$p\geq2$ が合成数なら $p=de$、$1< d< p$、$1< e< p$ と書ける。$p\mid de$ であるが、$0< d< p$ なので $p\nmid d$、同様に $p\nmid e$ であり、性質が成り立たない。対偶により、性質を満たす $p\geq2$ は素数である。
lem-prime-number-euclid は $p$ が素数であることを外すと成り立たない。$4\mid2\cdot2$ だが $4\nmid2$ であり、$6\mid2\cdot3$ だが $6\nmid2$、$6\nmid3$ である。より一般に、$\gcd(a,b)=1$ かつ $a\mid bc$ なら $a\mid c$ である（互いに素 の記事の命題「互いに素な因子の消去」）。帰納法により、積の因子が何個あっても同じことが言える。
$p$ を素数、$a_1,\dots,a_m$（$m\geq1$）を整数とする。$p\mid a_1a_2\cdots a_m$ ならば、ある $i$ について $p\mid a_i$ である。
$m=1$ なら明らかである。$m\geq2$ とし、$m-1$ 個の場合を仮定する。$a_1\cdots a_m=(a_1\cdots a_{m-1})a_m$ に lem-prime-number-euclid を適用すると、$p\mid a_1\cdots a_{m-1}$ または $p\mid a_m$ である。前者なら帰納法の仮定によりある $i\leq m-1$ で $p\mid a_i$ である。
lem-prime-number-euclid は、イデアル $(p)=p\mathbb{Z}$ が素イデアルであること、すなわち剰余環 $\mathbb{Z}/p\mathbb{Z}$ が整域であることを言っている。$\mathbb{Z}$ の素イデアルは $(0)$ と素数 $p$ に対する $(p)$ で尽くされ、$(p)$ は極大イデアルである（素イデアル の記事の定理「整数環と体上の多項式環の素イデアル」）。したがって $\mathbb{Z}/p\mathbb{Z}$ は $p$ 個の元からなる体であり、$\mathbb{F}_p$ と書く（有限体）。$n\geq2$ について $\mathbb{Z}/n\mathbb{Z}$ が整域であることと $n$ が素数であることは同値である（整域 の記事の命題「$\mathbb{Z}/n\mathbb{Z}$ が整域になる条件」）。
一般の整域では、lem-prime-number-euclid の性質をもつ元を素元、「単元でない 2 元の積に書けない」という性質をもつ元を既約元と呼んで区別する。整数ではこの 2 つは一致する（$\pm$ の違いを除いて素数）が、一般には一致しない。$\mathbb{Z}[\sqrt{-5}]$ では $6=2\cdot3=(1+\sqrt{-5})(1-\sqrt{-5})$ と 2 通りに分解され（単項イデアル整域 の記事の注意「反例：単項イデアル整域でない整域」）、既約元 $2$ は $(1+\sqrt{-5})(1-\sqrt{-5})$ を割り切るがどちらの因子も割り切らない。$N(a+b\sqrt{-5}):=a^2+5b^2$ は乗法的で、ノルム $2$ の元はないので $2$（ノルム $4$）は既約であり、$(1\pm\sqrt{-5})/2\notin\mathbb{Z}[\sqrt{-5}]$ なので $2$ はどちらの因子も割り切らない。単項イデアル整域では既約元は素元であり（同じ記事の補題「既約元は素元」）、$\mathbb{Z}$ はその例である。
素因数分解の存在と一意性
次の定理は 算術の基本定理（fundamental theorem of arithmetic）と呼ばれる。
$2$ 以上の任意の整数 $n$ は、有限個の素数の積
$$
n=p_1p_2\cdots p_r\qquad(r\geq1,\ p_1\leq p_2\leq\cdots\leq p_r)
$$
として書け、この表示はただ 1 通りである。すなわち、$n=q_1q_2\cdots q_s$（$q_1\leq\cdots\leq q_s$ は素数）を別の表示とすると、$r=s$ かつすべての $i$ で $p_i=q_i$ である。
存在：$n$ に関する強い帰納法（数学的帰納法）で示す。$n$ が素数なら $r=1$、$p_1=n$ でよい。$n$ が合成数なら $n=ab$、$1< a,b< n$ と書ける。帰納法の仮定により $a$ と $b$ はそれぞれ素数の積であり、それらを並べて小さい順に並べ替えれば $n$ の表示が得られる。
一意性：$n$ に関する強い帰納法で示す。$p_1\cdots p_r=q_1\cdots q_s=n$ とする。$p_1$ は $q_1\cdots q_s$ を割り切るので、cor-prime-number-product によりある $j$ で $p_1\mid q_j$ である。$q_j$ の正の約数は $1$ と $q_j$ だけであり $p_1\geq2$ なので、$p_1=q_j\geq q_1$ である。同様に $q_1$ はある $p_i$ に等しく $q_1\geq p_1$ である。よって $p_1=q_1$ である。
$r=1$ なら $n=p_1$ であり、$q_2\cdots q_s=n/q_1=1$ となるので $s=1$ である（$s\geq2$ なら左辺は $2$ 以上）。$s=1$ の場合も同様に $r=1$ である。$r,s\geq2$ なら、両辺を $p_1=q_1$ で割って $n':=p_2\cdots p_r=q_2\cdots q_s$ を得る。$2\leq n'< n$ なので、帰納法の仮定により $r-1=s-1$ かつ $i\geq2$ で $p_i=q_i$ である。
同じ素数をまとめると、$n\geq2$ は
$$
n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\qquad(p_1< p_2<\cdots< p_k\text{ は素数},\ e_i\geq1)
$$
とただ 1 通りに書ける。素数 $p$ が $n$ の分解に現れる指数を $v_p(n)$ と書き（現れなければ $0$）、$n$ の $p$ 進付値という（p進付値）。一意性から、正の整数 $d$ が $n$ を割り切ることは、すべての素数 $p$ で $v_p(d)\leq v_p(n)$ であることと同値である。実際、$n=dm$ なら $d$ と $m$ の分解を並べたものが $n$ の分解なので $v_p(n)=v_p(d)+v_p(m)$ であり、逆に指数の条件が成り立てば $m=\prod_pp^{v_p(n)-v_p(d)}$ とおけばよい。したがって正の整数 $a,b$ について
$$
\gcd(a,b)=\prod_pp^{\min(v_p(a),v_p(b))},\qquad \operatorname{lcm}(a,b)=\prod_pp^{\max(v_p(a),v_p(b))}
$$
である（最小公倍数）。たとえば $360=2^3\cdot3^2\cdot5$、$84=2^2\cdot3\cdot7$ から $\gcd(360,84)=2^2\cdot3=12$、$\operatorname{lcm}(360,84)=2^3\cdot3^2\cdot5\cdot7=2520$ である。
素数の分布
実数 $x$ に対し、$x$ 以下の素数の個数を $\pi(x)$ と書く（素数計数関数）。$\pi(10)=4$、$\pi(50)=15$ である。thm-prime-number-infinite は $\pi(x)\to\infty$（$x\to\infty$）を意味する。素数の個数がどのくらいの速さで増えるかを述べるのが次の定理である。
thm-prime-number-pnt を素数定理という。1896 年に Hadamard と de la Vallée Poussin が独立に、Riemannゼータ関数 $\zeta(s)$ が $\operatorname{Re}s=1$ 上で $0$ にならないことを用いて証明した。1949 年には Selberg と Erdős が複素解析を使わない初等的な証明を与えた。証明は Apo76 Chapter 13、HW08 Chapter XXII にある。より弱い評価、すなわち $x\geq2$ で $c_1\,x/\log x\leq\pi(x)\leq c_2\,x/\log x$ となる正の定数 $c_1,c_2$ が存在すること（Chebyshev の評価）は初等的に示せる（Apo76 Chapter 4）。
数値で見ると、比 $\pi(x)\log x/x$ は $1$ に近づくが、その近づき方は遅い。
| $x$ | $\pi(x)$ | $x/\log x$（概数） | $\operatorname{li}(x)$（概数） |
|---|---|---|---|
| $10^2$ | $25$ | $21.7$ | $30.1$ |
| $10^3$ | $168$ | $144.8$ | $177.6$ |
| $10^6$ | $78498$ | $72382.4$ | $78627.5$ |
素数は平均的にはこの密度で現れるが、隙間はいくらでも大きくなりうる。$n\geq2$ に対し、連続する $n-1$ 個の整数（$n!$ は階乗）$n!+2,\ n!+3,\ \dots,\ n!+n$ はすべて合成数である。$2\leq k\leq n$ について $k$ は $n!$ と $k$ をともに割り切るので $n!+k$ を割り切り、$1< k< n!+k$ だからである。一方で、$a$ と $n$ が互いに素なら、$n$ で割って $a$ 余る素数が無限に存在する（Dirichletの算術級数定理、Apo76 Chapter 7）。
関連項目
- 前提: 整数, 約数, Bézoutの等式
- 比較: 合成数, 素元, 既約元, 素イデアル
- 直後に読む: 素因数分解, 互いに素, 有限体, Eratosthenesの篩
- 発展: 素数定理, Riemannゼータ関数, 一意分解整域, Dirichletの算術級数定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
