素数が無限個あることの新証明

イントロダクション

素数が無限個あることの証明は、ユークリッドの証明、オイラーの証明などが知られています。

ユークリッドの証明は互いに素を用いた証明で、

オイラーの証明は調和級数が発散するということに基づいています。

最近、サイダックによる証明が発表されたようです。

サイダック[編集]

現代においても、新たな証明が次々に提案されている。その中でも、2006年に発表されたフィリップ・サイダックによる証明は非常に簡潔である[8]。

n は2以上の整数とする。n と n + 1 は互いに素なので、N2 := n(n + 1) は少なくとも2つの異なる素因子を持つ。同様に、N2 と N2 + 1 は互いに素なので、N3 := N2(N2 + 1) は少なくとも3つの異なる素因子を持つ。この操作を続けることにより、任意に多くの異なる素因子を持つ数を構成することができるので、素数は無数に存在する。

わからなかった方のために、nとn+1は互いに素になることの証明を書いておきます。

整数nとn+1の最大公約数をdと書くことにする。

ユークリッドの互除法から、n+1をnで割った余り1とnの最大公約数はdに等しい。

1とnの最大公約数は当然1なので、d = 1となる。

互いに素というのは、nとn+1の最大公約数が1であるという意味なので、

互いに素であることがわかった。

素数が無限個あることの新証明

このようにいくつもの証明が知られていますが、おそらく未発見の新証明を以前考えついたので、それをわかりやすくしたものを載せます。

この方法は、自然数の個数を利用した証明方法です。

[証明]

証明内で、以下の２つの事実あるいは定理を用います。

自然数は1と素数の積に分解される。(素因数分解の存在)
aを1よりも大きい実数、bを0以上の整数,nを自然数、cを実数とするとき、a^n > bn + cとなるnが必ず存在。

1.証明

素因数分解の存在は、素数が無限個あることを用いない証明が知られているので、

それを用います。

存在性

存在性定理の反例となる「素数の積で表せないような自然数」の存在を仮定すると、自然数の整礎性により、そのような数には最小の数（最小の反例）があるはずである。定義より 1 や素数は既に素数の積に表されているので、最小の反例 n は合成数であり、適当な自然数 a ≠ 1, b ≠ 1 をとれば n = ab とできるが、a < n かつ b < n ゆえ、n の最小性から右辺の各因子 a, b は素数の積として表され、n も素数の積で表せることとなり、矛盾する。ゆえに、任意の自然数は素数の積に表される。∎

2.の証明

$\displaystyle 式を変形して、a^n - bn -c \gt 0を満たすnを示す。$

$\displaystyle f(x) = a^x - bx - cを考え、f(x)がある区間で単調増加であることを示す。$

$\displaystyle f'(x) = a^x \log a - b, f'(x) = 0 ⇔ x = \log_{a}{\frac{b}{\log{a}}} = d$

$\displaystyle \log{a} \gt 0より、a^x \log{a}は狭義単調増加関数であるから、$

$\displaystyle x \gt dのとき、f'(x) \gt 0なので、$

$\displaystyle f(x)はx \gt dのとき増加する。$

$\displaystyle x → \infty とき、f(x)は収束しないことを示す。$

$\displaystyle f'(x)は、 x \gt dのとき単調増加で、\lim_{x \to \infty} f'(x)は発散するので、f(x)も発散。$

$\displaystyle よって、\lim_{x \to \infty} f(x) = \infty$

$\displaystyle 中間値の定理より、適当な正の整数nに対して、$

$\displaystyle 区間[n,\infty)でf(x) \gt 0となる。$

$\displaystyle x = nのとき、上記の式を得る。証明終わり$

[素数が無限個あることの新証明]

$\displaystyle 素数が有限個しかないと仮定する。$

$\displaystyle 適当に並べたi番目の素数をp_iとする。$

$\displaystyle 素数は有限なのだから、iも有限である。$

$\displaystyle 仮定と素因数分解の存在より、任意の自然数nは、$

$\displaystyle 0以上の整数x_1,x_2,x_3,....,x_iを用いて、$

$\displaystyle n = \prod_{s=1}^{i}p_s^{x_s}と表すことができる。$

$\displaystyle kを自然数とし、さらにnのk乗を考えて、n^k = \prod_{s=1}^{i}p_s^{kx_s}$

$\displaystyle さらに、n^k以下の自然数をaとすると、$

$\displaystyle 仮定より、任意の0以上の整数y_1,y_2,y_3,...,y_iを用いて、$

$\displaystyle a = \prod_{s=1}^{i}p_s^{y_s}という形式で表示でき、$

$\displaystyle さらに、aはn^k以下の自然数なので、$

$\displaystyle aはある素数p_iを有限個しか持てない。$

$\displaystyle 実際、n^k = p_i^{b}を満たす[b]個しか持てない。※[]はガウス記号$

$\displaystyle なぜなら、[b]+1個以上持つとn^kよりも大きい数になるので。$

$\displaystyle n^k = p_i^{b} ⇔ b = k\log_{p_i}{n}であるから、$

$\displaystyle aは下記の２つを満たさないといけない。$

$\displaystyle 1: a = \prod_{s=1}^{i}p_s^{y_s}$

$\displaystyle 2: 全てのiに対して、y_i \leqq [k\log_{p_i}{n}]$

$\displaystyle ここで、aの個数S(n^k)を考えてみると、$

$\displaystyle 全てのiに対して、p_iを0から[k\log_{p_i}{n}]以下までの任意の個数分だけ持つ。$

$\displaystyle これ以降、対数はp_sを底とする。$

$\displaystyle よって積の法則よりaの個数S(n^k)は、$

$\displaystyle \prod_{s=1}^{i}(k\log{n}+1)個以下であることがわかる。$

$\displaystyle 実際、S(n^k)はn^kなので、$

$\displaystyle 全てのkに対して、n^k \leqq \prod_{s=1}^{i}(k\log{n}+1)を満たさないといけない。$

$\displaystyle 言い換えれば、全てのkに対して、$

$\displaystyle \prod_{s=1}^{i}p_s^{kx_s} \leqq \prod_{s=1}^{i}(k\log\prod_{s=1}^{i}p_s^{x_s}+1)である。$

$\displaystyle ここで、a_s = p_s^{kx_s}, b_s = k\log\prod_{s=1}^{i}p_s^{x_s}+1 とおく。$

$\displaystyle 全てのsについて、b_s \lt a_sとなるkが存在することを示す。$

$\displaystyle 全てのsについて、\log nは0以上の整数, p_s^{x_s}は1以上の整数であるから、$

$\displaystyle 2.の証明よりb_s \lt a_sとなるkが存在。$

$\displaystyle よって、\prod_{s=1}^{i}b_s \lt \prod_{s=1}^{i}a_s$

$\displaystyle すなわち、\prod_{s=1}^{i}(k\log\prod_{s=1}^{i}p_s^{x_s}+1) \lt \prod_{s=1}^{i}p_s^{kx_s} となるkが存在。$

$\displaystyle これは、矛盾。$

$\displaystyle 証明終わり$

署名：tarotaro01204@gmail.com