素数

\( \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\LR}{\Leftrightarrow} \newcommand{\abs}[1]{\left\lvert #1 \right\rvert} \)

素数の概念は整数論において最も基本的なもののひとつであり、しかし素数そのものは単純な規則性を持たないように振る舞う。それゆえ素数についての命題は古くからの未解決問題として知られるものが多い。

本記事においては素数についての定義・基本的な性質、有名な結果についてのいくつかを紹介することにする。詳しい性質は以下の項目を参照。

• 素数の分布（初等的理論）

定義

自然数 $p$ が素数であるとは、$p>1$ であって、かつ $p$ の約数が $1$ または $p$ であることをいう。$n>1$ であって、素数でない整数 $n$、すなわち $2\leq d\leq n-1$ となる $n$ の約数 $d$ が存在する整数 $n$ を合成数という。

また $n$ の約数で、素数であるものを $n$ の素因数という。

定理1.1

• $(1)$ $p$ が素数で $a$ を割り切らないとき $\gcd(a, p)=1$ である。
• $(2)$ $p, q\geq 0$ が素数で $q\mid p$ ならば $p=q$ である。

Proof.

• $(1)$ $\gcd(a, p)$ は $p$ の正の約数なので $1$ または $p$ であるが、 $p$ は $a$ の約数ではないので $\gcd(a, p)\neq p$ である。

よって $\gcd(a, p)=1$ でなければならない。

• $(2)$ $p$ が素数で $q\geq 0$ は $p$ の約数なので $q=1$ または $q=p$ だが $q$ も素数だから $q=p$ である。

□

素因数分解

定理2.1

すべての $2$ 以上の整数は素因数をもつ。

Proof.

$N=2$ は素因数 $2$ をもつ。

$2\leq m\leq N-1$ となる整数 $m$ がすべて素因数をもつとする。 $N$ が素数ならば $N$ 自身が $N$ の素因数である。$N$ が合成数ならば $N$ は $2\leq d\leq N-1$ となる約数 $d$ をもつ。 倍数と約数: 定理2.2 (4)より $d$ の素因数は $N$ の素因数でもあるから、いずれの場合も $N$ は素因数をもつ。

よって数学的帰納法より、すべての $2$ 以上の整数は素因数をもつ。

□

定理2.2

すべての $2$ 以上の整数は素数の積 $p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ （$p_1, p_2, \ldots, p_k$ は相異なる素数）に分解される（その整数自身が素数の場合、つまり $k=1, e_1=1$ の場合も含む）。 このように、整数を素数の積に分解することを素因数分解という。

Proof.

$N=2$ は素数なので、$k=1, p_1=2, e_1=1$ とおくことで$1$つの素数の積に分解される。

$2\leq m\leq N-1$ となる整数 $m$ がすべて素数の積に分解されるとする。 $N$ が素数ならば $k=1, p_1=N, e_1=1$ とおくことで$1$つの素数の積に分解される。 $N$ が合成数ならば定理2.1より $N$ は素因数 $p$ をもつ。 $N$ は合成数だから $2\leq N/p\leq N-1$ なので、仮定より $N/p$ は素数の積に分解される。 よって $N=p\times (N/p)$ も素数の積に分解される。

よって数学的帰納法より、すべての $2$ 以上の整数は素数の積に分解される。

□

$1$ については $k=0$ とおくことで、$0$個の素数の積に分解されるとみることができる。 また負の数 $-N$ については、$N$ の素因数分解 $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ に対して、$-N=-p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ を $-N$ の素因数分解とみることで、$0$ 以外のすべての整数は素因数分解されると考えることができる。

しかし、素因数分解が存在することと、実際に与えられた整数の素因数分解を求めることができるかどうかは別の問題である。大きな整数の素因数分解を求めることは現時点では難しい問題である。

なお、ここでは素因数分解が存在することを示したが、さらに、整数の素因数分解は順序を除いて一意的であることを、倍数と約数の記事で示した形の初等整数論の基本定理を用いて後に示す。

素数の無限性

定理3.1

素数は無限に多く存在する。すなわち、任意の実数 $X$ に対して、$X$ より大きな素数が存在する。

Proof 1.

$X$ 以下の素数すべての積を $P$ とする。 定理2.1より $P+1$ は素因数 $p$ をもつ。 $p\leq X$ ならば $p$ は $P$ を割り切るが、このとき $p$ は $1=(P+1)-P$ も割り切ることになり、矛盾する。 よって $p>X$ となる。

□

なお、上記の数 $P+1$ 自体が素数であるとは限らない。 $$\begin{split} & 2+1=3, \\ & 2\times 3+1=7, \\ & 2\times 3\times 5+1=31, \\ & 2\times 3\times 5\times 7+1=211, \\ & 2\times 3\times 5\times 7\times 11+1=2311, \\ & 2\times 3\times 5\times 7\times 11\times 13+1=30031, \ldots \end{split}$$ のうち、最初の$5$つは素数だが、$30031=59\times 509$ は合成数である。

素数が無限に多く存在する証明は、このほかにも様々なものがある。

Proof 2.

$F_n=2^{2^n}+1 (n=0, 1, 2, \cdots)$ とおく。 各 $F_n$ は奇数である。また $m<n$ で $d>0$ が $F_m, F_n$ をともに割り切るならば $$F_n-2=2^{2^n}-1=(2^{2^m}-1)(2^{2^m}+1)(2^{2^{m+1}}+1)\cdots (2^{2^{n-1}}+1)=(2^{2^m}-1)F_m F_{m+1} \cdots F_{n-1}$$ より $d$ は $2$ を割り切る。よって $d=1$ または $2$ だが $F_n$ は奇数なので $d=1$ である。 定理2.1より各 $F_n$ の素因数 $p_n$ をひとつずつとることができるが、 $m\neq n$ のとき $\gcd(F_m, F_n)=1$ だから $p_m\neq p_n$ となる。よって $p_0, p_1, \ldots$ は素数の無限列となる。

□

$F_n$ をFermat数という。 $F_0=3, F_1=5, F_2=17, F_3=257, F_4=65537$ はいずれも素数である。 Fermatはこの形の数はそれ自体素数であると予想したが、Eulerは $$F_5=2^{2^5}+1=2^{32}+1=4294967297=641\times 6700417$$ が合成数であることを示した。その後も多くのFermat数が合成数であることが確かめられたが、素数であるFermat数は新たに知られておらず、$F_5$ から先のFermat数はすべて合成数と予想されている。

このようにして、素数にはいくらでも大きなものがあることがわかるが、やはり、巨大な素数に関する具体的な情報が得られるわけではない。巨大な素数を発見することは数論のひとつの課題である。2018年にGreat Internet Mersenne Prime Search により発見された $2^{82589933}-1$ が現在知られている最大の素数である。

初等整数論の基本定理

倍数と約数の記事で示した形の初等整数論の基本定理を用いて、整数の素因数分解は順序を除いて一意的であることを示す（通常は定理4.3を初等整数論の基本定理と呼ぶが、本質的なのは倍数と約数: 定理2.6であり、以下の議論は手続き的な議論である）。

定理4.1（初等整数論の基本定理2）

$p$ が $ab$ の素因数ならば $p$ は $a, b$ の少なくとも一方を割り切る。

Proof.

$p$ が $a$ を割り切らないならば定理1.1 (1)より $\gcd(a, p)=1$ だから、初等整数論の基本定理より $p$ は $b$ を割り切る。

□

定理4.2

$k\geq 2$ で $p$ が $a_1 a_2 \cdots a_k$ の素因数ならば $p$ は $a_i (1\leq i\leq k)$ の少なくとも$1$つを割り切る。

Proof.

$k=2$ のときは定理4.1そのものである。

$k=n-1$ のときに定理が成り立つとする。$p$ が $a_1 a_2 \cdots a_n$ の素因数ならば定理4.1より $p$ は $a_1 a_2 \cdots a_{n-1}$ または $a_n$ の少なくとも一方を割り切る。$p$ が $a_1 a_2 \cdots a_{n-1}$ を割り切るとき仮定より $p$ は $a_i (1\leq i\leq n-1)$ の少なくとも$1$つを割り切る。 よって、いずれの場合も $p$ は $a_i (1\leq i\leq n)$ の少なくとも$1$つを割り切る。

以上のことから、数学的帰納法より、定理は任意の $k\geq 2$ に対して成り立つ。

□

定理4.3（初等整数論の基本定理3）

$0$ 以外の任意の整数は順序を除いて素数の積に一意的に分解される。

Proof.

素因数分解が存在することは定理2.2より従う。

$N\neq 0$ が素数の積に $$\begin{split} N=& p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \\ N=& q_1^{f_1} q_2^{f_2} \cdots q_\ell^{f_\ell} \end{split}$$ と分解されているとする。ただし $p_1, p_2, \ldots, p_k$ は相異なる素数、$q_1, q_2, \ldots, q_\ell$ も相異なる素数とし、$e_1, e_2, \ldots, e_k, f_1, f_2, \ldots, f_\ell>0$ とする。

各 $q_s (1\leq s\leq \ell)$ は $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ を割り切るので、定理4.2より $q_s$ は $p_1, p_2, \ldots, p_k$ の少なくとも$1$つを割り切る。 $q_s$ および $p_1, p_2, \ldots, p_k$ は素数なので定理1.1 (2)より $q_s$ は $p_1, p_2, \ldots, p_k$ のいずれかと一致する。 同様にして各 $p_t (1\leq t\leq k)$ は $q_1, q_2, \ldots, q_\ell$ のいずれかと一致する。よって $k=\ell$ で、$p_1, p_2, \ldots, p_k$ と $q_1, q_2, \ldots, q_\ell$ は順序を除いて一致する。

$q_s=p_t$ とし、$f_s>e_t$ とすると $q_s^{f_s-e_t}$ は $N/q_s^{e_t}=N/p_t^{e_t}=\prod_{1\leq i\leq k, i\neq t} p_i^{e_i}$ を割り切るから $q_s=p_t$ は $\prod_{1\leq i\leq k, i\neq t} p_i^{e_i}$ を割り切る。よって定理4.2と定理1.1 (2)より $p_t$ は $p_i (1\leq i\leq k, i\neq t)$ のいずれかと一致するが、 $p_1, p_2, \ldots, p_k$ は相異なる素数となるようにとったことに矛盾する。よって $f_s\leq e_t$ である。同様に $e_t\leq f_s$ もいえるから $f_s=e_t$ でなければならない。

以上より、$p_1^{e_1}, p_2^{e_2}, \ldots, p_k^{f_k}$ と $q_1^{f_1}, q_2^{f_2}, \ldots, q_\ell^{f_\ell}$ は順序を除いて一致する。 よって $N$ は順序を除いて素数の積に一意的に分解される。

□

定理4.4

素因数分解の一意性から、与えられた整数の約数は素因数によって決定されることがわかる。すなわち $N=\pm p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と素因数分解すると、 $$d\mid N \Leftrightarrow d=\pm p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\ZZ, 0\leq f_i\leq e_i (1\leq i\leq k)$$

Proof.

$$\pm d=p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\ZZ, 0\leq f_i\leq e_i (1\leq i\leq k)$$ ならば $$N=\pm d p_1^{e_1f_1} p_2^{e_2-f_2} \cdots p_k^{e_k-f_k}$$ となるから、$d$ は $N$ の約数である（この証明において、$\pm$ のさす符号は必ずしも一致しない）。

$d$ が $N$ の約数とし $N=dm$ とおいて $$d=\pm q_1^{g_1} q_2^{g_2} \cdots q_\ell^{g_\ell}, m=\pm q_1^{h_1} q_2^{h_q} \cdots q_\ell^{h_\ell}, g_i, h_i\in\ZZ, g_i, h_i\geq 0$$ と素因数分解すると $$N=dm=\pm q_1^{g_1+h_1} q_2^{g_2+h_2} \cdots q_\ell^{g_\ell+h_\ell}$$ となるが、素因数分解の一意性から、 各 $j$ に対して $q_j=p_i, g_j+h_j=e_i$ となる $i$ が$1$対$1$に対応する。よって $p_i=q_j$ となる $i$ に対して $f_i=g_j$ とおくと $$d=\pm p_1^{f_1} p_2^{f_2} \cdots p_k^{f_k}, f_i\in\ZZ, 0\leq f_i\leq e_i (1\leq i\leq k)$$ となる。

□