Math Mar∞m

自由気ままに,書いていきます。

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

こんにちは。Math。です。

素数が無数に存在することはよく知られた事実で,さまざまな証明方法が知られています。

今回は,私が最近知った証明方法をご紹介します。

準備

証明に入る前に,次の補題を証明しておきます。

補題

任意の自然数  m に対して,


        (\log_2 N + 1)^m \lt N
    \tag{1}

を満たす  N\gt 0 が存在します。

一次関数と対数関数の発散スピードを比較すれば当然とも言えますが,一応,ちゃんと証明しておきます。

証明

 (1) のままだと扱いづらいので  c:=\log _ 2N+1 と置き換えると,式  (1) は次のように書き換えられます。


        c^m \lt 2^{c-1}
    \tag{2}

よって,式  (1) の代わりに式  (2) を示せば十分です。そこで,式  (2) を少し変形して,

 \displaystyle
        \frac{2^c}{c^m} \gt 2

が成り立つことを示します。

 2 ^ c=e ^ {c\ln 2} として, e ^ x の Taylor 展開(Maclaurin 展開)を考えると,

 \displaystyle
        e^{c\ln 2} = \sum_{k=0}^\infty \frac{1}{k!}(c\ln 2)^k \ge \frac{1}{(m+1)!}(c\ln 2)^{m+1}

という不等式を得ます1。よって,

 \displaystyle
        \frac{2^c}{c^m} \ge \frac{(\ln 2)^{m+1}}{(m+1)!}c

であり,左辺が 2 より大きくなればよいので, c

 \displaystyle
        c \gt \frac{2(m+1)!}{(\ln 2)^{m+1}}

となるように取ればよいことが分かります。

したがって,式  (2) を満たすような  c\gt 0 が存在します。すなわち,式  (1) を満たす  N\gt 0 が存在します。■

本題の証明

先ほどの補題を用いて,若干の組合せ論的に素数が無数に存在することを示します。ただし,2 が最小の素数であることは既知であるとします。

証明

自然数  m に対して,素数 m 個あると仮定します。以下,その  m 個の素数 p _ 1,\ldots,p _ m と表すことにします。

補題より,不等式  (1) を満たす  N\gt 0 が存在しますので, N 以下の自然数のうち


        p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}, \quad e_i \ge 0
    \tag{3}

の形で表せるものの個数  n について考えます。このとき,


        p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m} \le N

ですから, p _ i ^ {e _ i}\le N より  0\le e _ i\le\log _ {p _ i}N が成り立ちます。

ここで,2 は最小の素数なので  2\le p _ i です。よって, \log _ {p _ i}N\le\log _ 2N が成り立ちます。

さて,各  p _ i の指数  e _ i の取り方が  [\log _ {p _ i}N]+1 通り( [\ ]:Gauss 記号)あるので

 \begin{aligned}
        n &= ([\log_{p_1}N] + 1)([\log_{p_2}N] + 1) \cdots ([\log_{p_m}N] + 1)\\
        &\le (\log_{p_1}N + 1)(\log_{p_2}N + 1) \cdots (\log_{p_m}N + 1)\\
        & \le (\log_2N+1)(\log_2N+1) \cdots (\log_2N+1)\\
        &= (\log_2N+1)^m \lt N
    \end{aligned}

が成り立ちます。つまり, n N 未満です。

これより, N 以下の自然数の中に,式  (3) の形で表せない( p _ 1,\ldots,p _ m 以外の素因数を持つ)ものが存在します。これは, p _ 1,\ldots,p _ m 以外の素数が存在することを意味しますので,素数は少なくとも  m+1 個存在します。

したがって, m=1 から上記の議論を帰納的にくり返すことにより,素数が無数に存在することが分かります。■

おわりに

冒頭に「さまざまな証明方法」と述べましたが,正直に言いますと,ちゃんと噛み締めた証明方法は Euclid による方法Furstenberg 位相を用いた方法の 2 つだけです(今回の方法を合わせて 3 つです)。Wikipedia にはほかの方法も載っていますが,細部までは理解していません。

あと,解析学関連は気づかぬうちに循環論法になっていたりするので難しいですね…


  1.  e ^ x の定義によっては循環論法に陥りそうで怖いので,ここでは Taylor 展開の式で定義しておきます。