素数
素数の概念は整数論において最も基本的なもののひとつである。素数が重要なのは、あらゆる正の整数が素数の積として一意的にあらわすことができ、整数の乗法的な構造が素数によって説明されるからである。
しかし素数そのものは単純な規則性を持たないように振る舞う。それゆえ素数についての命題は古くからの未解決問題として知られるものが多い。
本ページおよび続くページにおいては素数の定義と基本的な性質を紹介することにする。詳しい性質を議論するには、別の準備が必要なので、後の節および章を参照されたい。
定義と自明な事実
自然数 $p$ が素数 (prime number) であるとは、$p>1$ であって、かつ $p$ の 約数 が $1$ または $p$ であることをいう。$n>1$ であって、素数でない整数 $n$、すなわち $2\leq d\leq n-1$ となる $n$ の約数 $d$ が存在する整数 $n$ を合成数 (composite)という。
つぎの事実がすぐにわかる。
- $p$ が素数で $a$ を割り切らないとき $\gcd(a, p)=1$ である。
- $p, q\geq 0$ が素数で $q\mid p$ ならば $p=q$ である。
- $\gcd(a, p)$ は $p$ の正の約数なので $1$ または $p$ であるが、 $p$ は $a$ の約数ではないので $\gcd(a, p)\neq p$ である。
よって $\gcd(a, p)=1$ でなければならない。 - $p$ が素数で $q\geq 0$ は $p$ の約数なので $q=1$ または $q=p$ だが $q$ も素数だから $q=p$ である。
素因数
$n$ の約数で、素数であるものを $n$ の素因数 (prime factor)という。
つぎのことがすぐにわかる。
すべての $2$ 以上の整数は素因数をもつ。
$N=2$ は素因数 $2$ をもつ。
$2\leq m\leq N-1$ となる整数 $m$ がすべて素因数をもつとする。
$N$ が素数ならば $N$ 自身が $N$ の素因数である。$N$ が合成数ならば $N$ は $2\leq d\leq N-1$ となる約数 $d$ をもつ。
倍数と約数: 定理2 (4)
より $d$ の素因数は $N$ の素因数でもあるから、いずれの場合も $N$ は素因数をもつ。
よって数学的帰納法より、すべての $2$ 以上の整数は素因数をもつ。
素数の無限性
素数は無限に多く存在する。すなわち、任意の実数 $X$ に対して、$X$ より大きな素数が存在する。
$X$ 以下の素数すべての積を $P$ とする。
定理2
より $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$ は合成数である。
素数が無限に多く存在する証明は、このほかにも様々なものがある。
$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
より各 $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数 (Fermat number)という。
$$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$ が現在知られている最大の素数である。
参考文献
