素数の無限性の一風変わった証明 - フィボナッチ・フリーク

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

私は証明そのものを鑑賞するのが好きなタイプなので、以前からずっと素数の無限性のオリジナル証明を作れないかと考えていたのですが、この間ついに組み合わせ論的な証明を思いつきました。組み合わせ論の最も美しい（？）定理の一つ、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)$ なので、 $a$ と $d$ で $p$ の指数の偶奇が等しいことから $v_p(a)\gt v_p(d)+1$ 。このとき $v_p(a+pd)=v_p(pd)=v_p(d)+1$ となって、 $a+pd$ と $a+d$ が同色であることに矛盾する。

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