ヘッダーイメージ 更新情報:HP
        東京理科大学理学部第一部数学科 教授 安部直人
本文へジャンプ

2014年01月19日 12時06分
素数の無限性

 先ず、背理法証明を考える:

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

 証明(背理法) 
  定理が成立しないとすると,素数は有限個である。[背理法の仮定]
 それらの素数を p1,p2,・・・, pn とする。
 このとき,q = (p1p2・・・pn)+1 を考えると,
 q は p1,p2,・・・, pn のどれでも割り切れない。
 したがって,q を素数の積として表したとき,
 この積に現れる素数は p1,p2,・・・, pn のいずれとも異なる。
 これは矛盾である。
 したがって定理が証明された。􀀀

 背理法だと、[背理法の仮定]から[矛盾]を導くまでの「背理法の主部」は、整合的に理解することは不可能です。これは直ぐに構成的な直接証明に直せます。

 直接証明1
  p_1, p_2, ・・・, p_n を相異なる n 個の素数とする。
 q = (p_1p_2・・・p_n)+1 とおく。
 p_1, p_2, ・・・, p_n は q の素因数ではない。
 q は 2 以上の自然数なので、素因数 p を持つ。
 p, p_1, p_2, ・・・, p_n は n+1 個の相異なる素数である。
 故に、素数は無限に存在する。􀀀

 直接証明2
  任意の素数 P につき、P 以下の素数の積を M とする。
 q=M+1 とおく。
 P 以下の素数は q の素因数ではない。
 q は 2 以上の自然数なので、素因数 p を持つ。
 p は P より大きい素数である。
 故に、素数は無限に存在する。􀀀

 共に、直接証明は新しい素数の見つけ方まで示唆している構成的な証明です。
新しい素数を見つけることは、公開鍵暗号の安全性が信じられている現在では大変に価値のあることです。
 量子コンピュータが実現されたら無価値ですが、上記のような当たり前なことに背理法を使う文化レベルではいつになるやら?

 なお、直接証明の途中に使った自明な事実
「任意の隣接する 2 整数は互いに素 」
「互いに素な 2 整数は共通素因数を持たない」
から、次のように新しい素数の見つけ方も考えられます。

 直接証明3
  任意の自然数 m につき、m(m+1) をとれば、
 「 m の素因数の集合(種類)は、
 m(m+1) の素因数の集合(種類)の真部分集合である」
 これは任意の回数繰り返すことが可能である。
 故に、素数は無限に存在する。􀀀

 これは、無限に狭義単調増加する素数の集合を与えています。

フッターイメージ