フィボナッチ・フリーク

数学の小ネタ集。

素数の無限性の一風変わった証明

素数が無限に存在することはもはや人類の常識と言えますが、その証明を沢山知っている人は少ないように感じます。

私は証明そのものを鑑賞するのが好きなタイプなので、以前からずっと素数の無限性のオリジナル証明を作れないかと考えていたのですが、この間ついに組み合わせ論的な証明を思いつきました。組み合わせ論の最も美しい(?)定理の一つ、Van der Waerdenの定理を使う証明です。

定理(Van der Waerden). 正整数全体をどのように有限色で塗り分けても、任意の長さの同色の等差数列が存在する。

この定理の証明は以下の記事などに紹介されています。

integers.hatenablog.com

しかし残念なことに、関連するキーワードで検索したところ、私の考えたものとほぼ同じ証明が既に別の人(L. Alpoge氏)によって発表されていました。しかも私の証明には穴があって、彼の論文ではそれが埋められていることにも気づきました。数学の世界は厳しいですね!

そういうわけで悔しいのですが、せっかくなので今回は彼の証明を紹介したいと思います。今回の記事では正整数n素数pで割れる回数をv_p(n)で表します。

定理. 素数は無限に存在する。

証明. 素数が有限個だったと仮定すると、正整数全体を「素因数に現れる素数の種類とそれぞれの指数の偶奇」を色として塗り分けることができる。どの素数の2乗よりも大きい正整数rをとると、Van der Waerdenの定理よりa,a+d,\cdots,a+drという同色の等差数列が存在する。このときaの任意の素因数pについてp\mid a+dだからp\mid d

(1) v_p(a)\gt v_p(d)とするとv_p(a+d)=v_p(d)\lt v_p(a)なので、adpの指数の偶奇が等しいことからv_p(a)\gt v_p(d)+1。このときv_p(a+pd)=v_p(pd)=v_p(d)+1となって、a+pda+dが同色であることに矛盾する。

(2) v_p(a)=v_p(d)とするとa=p^nA, d=p^nDA,Dpと互いに素)と書ける。\mathrm{mod}~p^2でのDの逆元*1E をとりk\equiv(p-A)E~\mathrm{mod}~p^21\leq k\lt p^2)と置くと

A+kD=A+(p-A)ED\equiv p~\mathrm{mod}~p^2

なので

v_p(a+kd)=v_p(p^n(A+kD))=n+1

となり、aa+kdが同色であることに矛盾する。

以上からv_p(a)\lt v_p(d)なのでv_p(a+d)=v_p(a)。これが任意のpについて成り立つのでa=a+dとなり矛盾する。ゆえに素数は無限個存在する。~~~\square

 

綺麗な証明かと言われれば微妙ですが、これはこれで面白い気がしませんか?

*1:DE\equiv 1~\mathrm{mod}~p^2なる数