ホーム >> 整数 >> 素数が無限に存在することの証明

素数が無限に存在すること証明を $3$ 通り紹介します.



⇨予備知識

・背理法
・数学的帰納法
・ $n$ と $n+1$ は互いに素
・ $1$ 以上の整数は必ずひとつ以上の素因数をもつ


素数は無限に多く存在する

素数とは,$1$ より大きく,$1$ と自分自身以外に約数をもたない自然数のことです.小さい順に, $$2,3,5,7,11,13,17,19,23...$$ とつづいていきます.実は,素数が無限に多く存在することが紀元前 $3$ 世紀ごろのユークリッドの著書「原論」ですでに証明されています.

最も有名な証明

以下の証明は,ユークリッドが実際に書いた証明とは若干異なりますが,似たような方法です.

証明: 背理法で示す.素数が有限個しかないと仮定する.$p_1 < p_2 < \cdots < p_n$ をすべての素数とする. $$N=p_1p_2\cdots p_n +1$$ とおくと,$N$ は $p_1,...,p_n$ のいずれでも割り切れない (つまりすべての素数で割り切れない) ので,素数である.しかし,$N$ は $p_1,...,p_n$ のいずれでもないので,矛盾である.したがって,素数は無限に存在する.


ひとつ注意すべきことは,上の証明を見て,『有限個の素数 $p_1,...,p_n$ が与えられたら,$p_1p_2\cdots p_n+1$ は素数』と思ってはいけません.この命題は偽です.実際,$3\cdot 5+1=16$ という簡単な反例が存在します.

上の証明では,素数が有限個しかないという (実際には偽であるような) 仮定のもとで議論を行っているので,そのようなことが起こるのです.

フェルマー数を利用する証明

背理法を使わず,直接証明することもできます.

ゴールドバッハはフェルマー数の性質を使って証明しました.
フェルマー数とは,$2^{2^n}+1$ の形で表される自然数のことです.
つまり, $$F_n=2^{2^n}+1  (n=0,1,2,...)$$ とおいたとき,$F_n$ を $n$ 番目のフェルマー数と呼びます.フェルマー数は小さい順に, $$3,5,17,257,65537,...$$ とつづいていきます.

つぎのふたつの事実が成り立つことはすぐにわかります.
・フェルマー数は無限に存在する
・すべてのフェルマー数は奇数である

さらに,フェルマー数は以下の漸化式が成り立ちます.

フェルマー数の漸化式: $F_n=2^{2^n}+1$ をフェルマー数とする.このとき,次の漸化式が成り立つ. $$\large F_n=F_0F_1\cdots F_{n-1}+2  (n \ge 1)$$

証明: 数学的帰納法で示す.
$n=1$ のときは,$F_1=F_0+2$ なので成り立つ.
$$ F_n=F_0F_1\cdots F_{n-1}+2$$ が成り立つと仮定すると, $$F_{n+1}=2^{2^{n+1}}+1=(2^{2^n}+1)(2^{2^n}-1)+2=F_n(F_n-2)+2$$ $$=F_n(F_0F_1\cdots F_{n-1})+2  (\leftarrow \text{帰納法の仮定より})$$ $$=F_0F_1\cdots F_{n-1}F_n+2$$ となる.したがって, $$F_n=F_0F_1\cdots F_{n-1}+2  (n \ge 1)$$ が成り立つ.


この漸化式から,フェルマー数に関するつぎの重要な性質が導かれます.

フェルマー数の性質: 相異なるフェルマー数は互いに素である.

証明: $F_n=2^{2^n}+1$ をフェルマー数とする.
相異なるフェルマー数 $F_n,F_m (n < m)$ を任意に選ぶ.$m$ について,さきほど示した漸化式を考える. $$F_m=F_0F_1\cdots F_{m-1}+2$$ $d$ を $F_n,F_m$ の公約数とすると,$d$ は $F_m,F_0F_1\cdots F_{m-1}$ をともに割り切るので,上の式から,$d$ は $2$ を割り切る.したがって,$d=1,2$ であるが,すべてのフェルマー数は奇数なので,$d=1$.よって,$F_n,F_m$ は互いに素.


では,フェルマー数をつかって,素数が無限にあることを証明してみましょう.

素数が無限に存在することの証明: 各フェルマー数 $F_n$ $(n \ge 0)$ に対して,その素因数 $p_n$ をそれぞれひとつ選ぶ.すると,相異なるフェルマー数は互いに素なので,$p_0,p_1,...$ は相異なる素数でなければならない.したがって,フェルマー数は無限に存在するので,素数も無限に存在する.

簡潔な証明

2006年,Filip Saidak は非常に簡潔な証明を提出しました.

素数が無限に存在することの証明 (Saidak): 自然数 $n >1 $ をひとつ選ぶ.$n,n+1$ はともにひとつ以上の素因数をもっており,$n,n+1$ は互いに素なので, $$N_2=n(n+1)$$ とおくと,$N_2$ は $2$ つ以上の素因数をもっている.さらに,$N_2,N_2+1$ は互いに素なので, $$N_3=N_2(N_2+1)$$ とおくと,$N_3$ は $3$ つ以上の素因数をもっている.この操作は無限に繰り返すことができる.したがって,いくらでも多くの素因数をもつ数が構成できるので,素数は無限に存在する.