インテジャーズ

インテジャーズ

数、特に整数に関する記事。

ユークリッド数と素数の無限性

59は合成数であるような最小のEuclid数30031の小さい方の素因数です
(30031=59×509)。

まず、素数が無数に存在することの恐らく最も有名である証明を紹介します。

補題 \ 2以上の自然数は必ず素因数をもつ。

証明. n \geq 2を考える。nが素数ならば、それが素因数なので証明は終了する。そこで、nが合成数であると仮定しよう。すなわち、n=abと書けたとする(ただし、a, bは2以上の整数)。すると、もしaが素因数をもてば、nも素因数をもつことになり、証明は終了する。つまり、問題はnより小さいaに帰着された。aが素数でなければ同じように、より小さい数へと問題を帰着させていくことにより、いつか素数にたどり着く(自然数全体集合は整列集合なので、このような分解が無限に続くことは決して起こりえない)。その素数が所望の素因数である。 Q.E.D.

素数が無数に存在することの証明(背理法による)
素数がこの世に有限個(N個)しかなかったと仮定する。素数を小さい順にp_1, \dots, p_Nとし、それらを全て掛け合わせて1足した数p_N \# +1 = p_1p_2\cdots p_N+1を考える。p_N \# +1p_1, \dots, p_Nのどれでも割り切れない(割ると1余る)。これは上記補題によってp_N \# +1が素因数をもつことに矛盾する。 Q.E.D.

素数階乗 p_N\#については次の記事を参照してください:
integers.hatenablog.com

この証明を受けて、E_n := p_n\# +1のことをnEuclid数といいます。上記証明を初めて見た人の中には「E_Np_1からp_Nのどの素数でも割り切れないのでE_Nも素数である」という間違った論証をしてしまうことがありますが、それは論理の飛躍を起こしてしまっています。実際に、E_nは合成数の場合もあります。それでは、いくつかのEuclid数とその素因数分解をみてみましょう:

E_1=3,
E_2=7,
E_3=31,
E_4=211,
E_5=2311,
E_6=30031=59 \times 509,
E_7=510511=19\times 97\times 277,
E_8=9699691=347\times 27953,
E_{9}=223092871=317\times 703763,
E_{10}=6469693231=331\times 571\times 34231,
E_{11}=200560490131,
E_{12}=7420738134811=181\times 60611\times 676421,
E_{13}=304250263527211=61\times 450451\times 11072701,
E_{14}=13082761331670031=167\times 78339888213593,
E_{15}=614889782588491411=953\times 46727\times 13808181181,
E_{16}=32589158477190044731=73\times 139\times 173\times 18564761860301,…

未解決問題1 素数であるようなEuclid数は無数に存在するか?

未解決問題2 合成数であるようなEuclid数は無数に存在するか?


なお、「Euclid数」という用語は非常に混乱する名前で、「Euclidによる上記素数の無限性証明に冠して」付けられた名前なのですが、実は上記証明はEuclidによるものではありません。というのも、Euclid自身による証明は次のように背理法を使っていません:

素数が無数に存在することのEuclidによる証明 (原文ではない*1 )
n個の素数q_1, \dots, q_Nが手中にあるとする*2。このとき、A_N:=q_1\times \cdots \times q_{N}+1を考える。補題によって、A_N\geq 2は素因数q_{N+1}をもつ。ところが、A_Nq_1, \dots, q_Nのいずれでも割り切れないので、q_{N+1}q_1, \dots, q_Nのいずれとも異なる。すなわち、我々はN+1個目の素数を手中にすることができた。Nは任意なので素数は無数に存在することがわかる。Q.E.D.

Euclidの方法において、q_{N+1}としてA_Nの最小の素因数を選んでいくことにしてq_1=2からスタートすると、次のようになります:

2→3→7→43→13→53→5→6221671→38709183810571→139→2801→11→17→5471→…

例えば、A_4=1807=13\times 139なのでq_5=13といった感じです。つまり、Euclidの証明法はEuclid数とは無関係であることがわかります(直後に述べるようにEuclid数で証明を書くこともできます)。上の数列をEuclid素数列(またはEuclid–Mullin数列)とよびます。このとき、次の予想は未解決問題です。

Shanks予想
Euclid素数列に現れる数の全体のなす集合は全ての素数のなす集合に一致する。すなわち、Euclid素数列には全ての素数が一回ずつ現れる。

また、Euclidの証明手法を応用すれば、n番目の素数p_nの上からの評価を得ることもできます。Euclidの証明において、q_1=p_1, \dots, q_N=p_Nだったとします。そうしてq_{N+1}を得ると、p_{N+1}がその数までに存在することが確定するため、有限通り調べることによってp_{N+1}を得ることができます。そうして、q_{N+1}=p_{N+1}として議論を進めることができます:

定理 \ \ p_n < 2^{2^n}.

証明. nに関する数学的帰納法で証明する。p_1=2 < 2^{2^1}=4である。nのとき成立すると仮定すると、

p_{n+1} \leq p_1\times \cdots \times p_n +1 <2^{2^1}\times 2^{2^2} \times \cdots \times 2^{2^n}+1 = 2^{2^1+2^2+\cdots +2^n}+1 < 2^{2^{n+1}}

を得る。最後の不等号では等比数列の和の公式を使っている。 Q.E.D.


素数の無限性証明は170通り以上知られており、私はマニアなので今後も多数紹介していくことになると思いますが、この記事ではEuclidの証明と関係する別証明を2つ紹介したいと思います。

1つ目はF. Saidak, A new proof of Euclid's theorem Amnerican Math. Monthly 9 Vol l13, No. 10, December 2006. による証明です。これは、Euclidの証明より簡単な証明が2000年ぶりに発見されたといくつかの文献で引用されています。

Saidakによる証明
nを2以上の整数とする。補題よりnは素因数をもつ。こうして我々は素数を1つ手に入れた。次にN_2 := n(n+1)とする。nn+1は互いに素なので、n+1の素因数はnの素因数とは異なる。つまり、N_2の素因数として我々は素数を2つ手に入れた。次にN_3 := \{n(n+1)\} \{n(n+1)+1\}とする。n(n+1)n(n+1)+1は互いに素なので、n(n+1)+1の素因数はN_2の素因数とは異なる。つまり、N_3の素因数として我々は素数を3つ手に入れた。このプロセスを続ければ素数が無数に手に入る。 Q.E.D.

Saidakの証明はEuclidの証明と同じく直接法です。では、どの点がEuclidの証明より優れているのでしょうか?
(なお、SaidakはEuclidが背理法を用いて証明したと記述しているので、その点をもって自分の証明の方がシンプルであると主張している彼の主張はナンセンスというか完全に誤りです。)
見た目上はある意味Saidakの方がシンプルに見えますが、2つの証明は使う構造は全く一緒(「ある数+1」を考えることが重要で、基本原理はnn+1が互いに素であること)で、使う数列のみが異なると言えます(Saidakはシンプルに見せるためにわざとN_3までしか書いていないのだと思いますが、厳密には数学的帰納法で記述する必要があり、そうなると文章量および文のシンプルさだけではEuclidの証明と大差はありません)。n=2からスタートさせて、Saidak数列S_NS_0=2, \ S_k = S_{k-1}(S_{k-1}+1)で定義します。N個の素数があったとき、Euclidの証明ではそれらの素数を用いてA_Nを定義し、N+1個目の素因数の存在を示しています。それに対して、Saidakの証明ではS_NN個以上素因数をもつことは確実ですが、それを定義するのに素因数の情報は一切用いる必要がありません。この部分(S_Nの定義の簡単さ)がSaidakの証明の数学的観点から見たシンプルさです。逆に言えば、Euclidの方がシャープな数列を用いているので優れているとも言えます。

実際のところ、Saidakの証明のよさは数学的な観点より、q_1, \dots, q_Nという添え字付きのちょっと複雑な数式は使わず、n(n+1)のような中学一年生でもわかるような数式しか使わないという、見せ方のシンプルさなのでしょう。


2つ目に紹介するのは、背理法による証明と構造は全く同じなのですが、見せ方を変えたものです:
S. Northshield, A nne-line proof of the infinitude of primes, Amer. Math. Monthly Volume 122, Number 5, May 2015, 466-466(1).

素数の無限性の一行証明 (by Northshield)
\displaystyle 0 < \prod_p \sin \left( \frac{\pi}{p} \right) = \prod_p \sin \left( \pi \frac{1+2\prod_{p'}p'}{p} \right) = 0.

証明の解説. 素数が有限個しかなかったと仮定します。p_1, \dots, p_nが全ての素数であるとしましょう。このとき、N := p_1\times \cdots \times p_nという整数を作れます。定義から任意の素数p_iに対してN/p_i \in \mathbb{Z}が言えます。よって、1\leq i \leq nなる各iに対して

\displaystyle \sin \frac{\pi}{p_i} = \sin \pi \frac{1+2N}{p_i}

が成り立ちます(正弦関数は周期2\piである)。一方、補題より1+2Nは素因数をもつため、あるp_iで割り切れます。よって、そのようなiに対して

\displaystyle \sin \frac{\pi}{p_i} = \sin \left( \pi\frac{1+2N}{p_i} \right) =0

が成り立ちます(整数mに対して\sin \pi m = 0)。つまり、

\displaystyle 0 < \prod_{i=1}^n\sin \frac{\pi}{p_i} = \prod_{i=1}^n \sin \left( \pi \frac{1+2N}{p_i} \right) = 0

となって矛盾します。 Q.E.D.

最初の証明では補題によって存在する素因数で割っても1余るため矛盾したわけですが、この証明ではその部分を正弦関数に担ってもらったというわけです。

解説を省いて短くしたいんだったら、最初の証明を「背理法、1+\prod_pp」とでもした方が短いですよね笑。ただ、整数論的な議論において三角関数が活躍することはよくあります。

最後に紹介した2つの証明は、有名な古典的証明と同じような証明でしたが、面白い別証明も存在します。本質的に異なる証明は意義がそれなりにあります。それらは他の記事で紹介していく予定です。

*1:f:id:integers:20160802112253p:plain

*2:p_nn番目の素数の記号として使うことが多いので、ここではq_nを採用しました。