素数が無限に存在することの証明

素数は無限に存在します

素数が無限に存在することは、今から 2000 年以上も昔に証明されています。ユークリッドの『原論』第9巻命題20には驚くほど簡単な証明法が載せられています。

【証明①】ユークリッド『原論』に記載された方法です。背理法で証明します。
素数が有限個 ($k$ 個) しかないと仮定しましょう。
$$p_1,p_2,\cdots p_k$$
これ以外はすべて合成数です。この有限個の素数を用いて新しい数をつくります。
$$N=p_1{p}_2\cdots p_k+1$$
この数はどの素数とも異なっているので合成数です。つまり有限個の素数のうちどれかで割り切れるはずです。しかし、どの素数 $p_i$ で割っても必ず 1 が余ります。これは合成数であることに矛盾しているので、やはり素数は無限個存在することになります。（証明終）

【証明②】① の方法が最も有名でエレガントな証明法ですが、素数が無限に存在することは数論の根幹をなす重要な定理なので、現代に至るまで各時代で他にもたくさんの証明法が考え出されてきました。ここでは、その中からオイラーによる証明法を紹介しておきます。ただし無限等比級数の公式など、数学Ⅲ程度の予備知識は必要です。

ある素数 $p_i$ について、$1/p_i<1$ なので、無限等比級数の公式を用いて
$$\begin{array}{}\text{(1)}& \frac{1}{1-\frac{1}{p_i}}=1+\frac{1}{p_i}+\frac{1}{p_i^2}+\cdots \end{array}$$
のように級数展開することができます。ここで素数は有限個しか存在しないと仮定します。
$$p_1,p_2,\cdots p_k$$
これらの素数について (1) 式をつくり、それを全て掛けます。
$$\begin{array}{}\text{(2)}& \prod _{i=1}^k\frac{1}{1-\frac{1}{p_i}}=(1+\frac{1}{p_1}+\frac{1}{p_1^2}+\cdots )(1+\frac{1}{p_2}+\frac{1}{p_2^2}+\cdots )\cdots \end{array}$$
ここで ${\displaystyle \prod _{i=1}^k}$ は $1$ から $k$ までについて積をとるという記号です。右辺を展開すると各項の分母は
$$\begin{array}{}\text{(3)}& p_1^{a_1}{p}_1^{a_2}\cdots p_1^{a_k}\end{array}$$
という形になりますが「素因数分解の仕方が一通りである」という定理から、(3) には全ての自然数が重複せずに現れるはずです。すると (2) の右辺は
$$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots$$
と書けますが、これは調和級数なので +∞ に発散してしまいます。しかし (2) の左辺は有限個の積ですから、その値は有限となるはずなので矛盾しています。したがって素数は無限に存在します。（証明終）

互いに素である2数の積がc^nである場合に成り立つ定理

たとえば平方数 36 は
$$2\times 18,3\times 12,4\times 9,6\times 6$$
のように分解できますが、この中で 4 と 9 は互いに素であり、ともに平方数となっています。この事実を一般化したのが次の定理です。

【証明】$c$ を素因数分解して
$$p_1^{s_1}{p}_2^{s_2}\cdots p_k^{s_k}$$
のように書けたとすると、$ab=c^n$ より
$$ab=p_1^{n{s}_1}{p}_2^{n{s}_2}\cdots p_k^{n{s}_k}$$
となります。右辺の因数が $a,b$ に分配されますが、$(a,b)=1$ なので、ある素因数 $p_i$ について、$a,b$ どちらかの因数にしかなりません。すなわち
$$\begin{array}{}\text{(1)}& p_i|a,p_i\mid /b\end{array}$$
であるのか、
$$\begin{array}{}\text{(2)}& p_i\mid /a,p_i|b\end{array}$$
のどちらかであるということです。よって、ある一種類の因数は $a$ か $b$ のどちらか一方にまとめて入ります。それが仮に (1) のケースであるとすれば
$$p_i^{n{s}_i}|a$$
のようになるので、$a,b$ はともにある整数の $n$ 乗となります。（証明終）

定理 B8 で $n=2$ のときは次のように書けます。

完全平方数とは整数の平方数 1, 4, 9, 16, … のことです。単に平方数とよぶほうが一般的です。ある平方数を素因数分解してみれば、互いに素である平方数の組をみつけられる場合もあります（もちろん存在しない場合もあります）。たとえば平方数 144 は
$$144=3^2\times 2^4=9\times 16$$
と分解することができて、9 と 16 はそれぞれ平方数であり互いに素です。しかし平方数の積で表せるからといって、必ずしも互いに素であるとは限りません（定理の逆は成り立ちません）。たとえば平方数 64 は
$$64=2^6=4\times 16$$
のように 2 つの平方数の積で表せますが、4 と 16 は互いに素ではありません。

ついでに $n=3$ の場合も定理として載せておきます。

完全立方数とは整数の 3 乗数 1, 8, 27, 64, … のことです。こちらも普段は単に立方数とよびます。たとえば立方数 216 は
$$216=2^3\times 3^3=8\times 27$$
と分解できて、8 と 27 はそれぞれ立方数であり、互いに素の関係にあります。

【関連記事】1が素数ではない理由