初等整数論/素数

本記事では、いよいよ初等整数論の中心的概念というべきであり、様々な問題の源泉でもある、素数について述べる。

素数・合成数

自然数内で考える。1 以外の自然数は次の2つに分類できる。

• 1 とそれ自身以外の約数を持つ数
• 1 とそれ自身以外に約数を持たない数

前者は合成数といい、後者は素数という。奇数の素数を奇素数という。素数は小さい順から、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... と続いていく。また、合成数を素数のみの積にすることを素因数分解という。

このとき以下のような疑問が生ずる。

• 素数は無限に存在するのだろうか?
• 素数の分布はどうなっているのだろうか?
• 素数の一般項はなんだろうか?
• 素数には、(3, 5), (5, 7), (11, 13), (17, 19), など隣り合う奇数がどちらも素数になっているということが起こるが、このような組は無限に存在するのだろうか?

中には初等的な議論で証明できるものもあるが、多くは難問で現在もよく分かっていないものが多い。

定理 1.10

任意の合成数は素因数分解される。

証明
最小の合成数 4 は $4=2\cdot 2$ と素因数分解される。仮に $n$ より小さい任意の合成数について定理が成り立っていたとする。すると、定義より $n=ab$ となる。このとき、$a,b<n$ だから、これらが素数のときは定理の主張を満たし、合成数の場合素因数分解され、よって $n$ も素因数分解される。

以上より累積帰納法から、定理が証明される。

例

$65=5\cdot 13$

定理 1.11

素数は無限に存在する。(参考 : w:素数が無数に存在することの証明)

証明 1
仮に素数が有限個だとすると、最大の素数 $p$ が存在する。このとき、全素数をかけあわせ 1 足した数を考える。すなわち、

$q=2\cdot 3\cdot 5\cdots p+1$

このとき、もちろん $q>p>1.$

q は合成数ではない。なぜなら、$2m+1$ という形をしており、1余るので、$2$ の倍数ではないからである。また同様に、$3$ の倍数でも、$5,\cdots p$ の倍数でもない。したがって定理 1.10 より、これは素数にほかならない。しかし、これは $p$ の最大性に反する。

以上より、素数は無限個あると分かる。

注意 : + 1 ではなく - 1 にしても同様に証明できる。

証明 2
$(n,n+1)=1$ である。なぜなら、仮に $(n,n+1)=g>1$ ならば、定理 1.1 より $g\,|\,(n+1)-n\iff g\,|\,1$ となり矛盾するからである。

よって、適当に数 $N_{0}>1$ を取ってくる。すると、$N_{1}=N_{0}(N_{0}+1)$ は、互いに素な2数をかけているから、定理 1.10 より少なくとも2つは異なる素因数を持つ。次に、$N_{2}=N_{1}(N_{1}+1)$ とすると、次に述べる算術の基本定理から、少なくとも異なる素因数を3つは持つ。これを繰り返していけばいくらでも素数が生成できる。よって素数は無限に存在する。（循環論法にはなっていない）

証明 3
フェルマー数 を $F_{n}=2^{2^{n}}+1$ と定義する。そして、数学的帰納法によって $F_{n}=F_{1}F_{2}F_{3}\cdots F_{n-1}+2$ を証明する。

すると、任意の異なるフェルマー数についてそれらは互いに素である。なぜなら、とある $F_{n},F_{m}$ について最大公約数が1以上の数 $g$ だったとすると、 $n>m$ とすれば $F_{n}=F_{1}F_{2}F_{3}\cdots F_{m}\cdots F_{n-1}+2$ となり、$g$ は 2を割りきらなければならず、$g>1$ より $g=2.$

しかし、フェルマー数は明らかに奇数。よって矛盾を起こし、主張は証明された。

証明 2 と同様、新しいフェルマー数を考えると先ほどの議論から、異なる素因数を見つけることができる。よって素数は無限に存在する。

注意 : $q=2\cdot 3\cdot 5\cdots p+1$ の形の数をユークリッド数という。この形の数自体が素数であるとは限らない。たとえば $p=13$ のとき $q=2\cdot 3\cdot 5\cdots 13+1=59\cdot 509$ である。$p=2,3,5,7,11,31,379,1019,1021,2657,3229,4547,4787,11549,13649,18523,23801,24029,42209,145823,366439,392113$ のときユークリッド数は素数になることが知られている。素数であるユークリッド数が無限にあるか否か、合成数であるユークリッド数が無限にあるか否か、未だわかっていない。

同様に、フェルマー数自体が素数であるとは限らない。フェルマーは $F_{0}=3,F_{1}=5,F_{2}=17,F_{3}=257,F_{4}=65537$ が素数であることを確かめ、フェルマー数はすべて素数だろうと予想したが、オイラーは $F_{5}=4294967297=641\cdot 6700417$ であることから $F_{5}$ は素数でないことを示した。その後 $n=6,7,8,\ldots ,32,36,37,38,39,42$ など多くの n について $F_{n}$ が素数でないことが示されている。フェルマー数で素数であるものは 最初の5つしかないと予想されているが、これも未だにわかっていない。

素数判定

定理1.11 に書いた通り素数は無限に多くあるが、与えられた数が素数かどうか確かめるにはどのようにすればよいだろうか？ 定義によれば素数は 1 とその数自身以外に約数を持たない数である。N の約数は N 自身を除けば N よりは小さいから、2 から N-1 までの数の中に N の約数が1つでもないか確かめればよいことがすぐにわかる。

さらに、次の事実がわかる。

補題

N が合成数ならば N は $1<d\leq {\sqrt {N}}$ の範囲に約数 d をもつ。

実際 N が合成数で ${\sqrt {N}}<m<N$ の範囲に約数 m を持つとき $d=N/m$ も N の約数で $1<d\leq {\sqrt {N}}$ となる。

したがって、N が素数かどうか確かめるには ${\sqrt {N}}$ までの数のみを確かめれば良い。 しかし、これでも N が大きいときには計算に非常に時間を要するため、素数判定法としては実用的ではない。より高速な素数判定法が求められる。実際、現在では log N の多項式程度の時間で可能な素数判定法が知られている。