じぶん更新日記

1997年5月6日開設
Copyright(C)長谷川芳典



01月のインデックスへ戻る
最新版へ戻る

　夕日に照らされるプラタナス。樹皮に趣がある。関連記事がこちらや、こちらにあり。新宿御苑のプラタナスとは樹形が異なっている。


2015年01月28日（水）

【思ったこと】
150128（水）オックスフォード白熱教室(11)素数が無限にあることの証明

　1月26日の続き。

　番組では、素数ゼミの話題に続いて、素数が無限に存在することについてのユークリッドの証明が紹介された。ウィキペディアの当該項目から引用すると、以下のようになる。
素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。
　もっとも、リンク先でも指摘されているように、この証明はユークリッドの『原論』では、
a, b, …, k を任意に与えられた素数のリストとする。その積 P := a × b × … × k に 1 を加えた数 P + 1 は、素数であるか、素数でないかのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。
というのが正確な表現であり、以下の文は、ユークリッドの証明を誤解しているという。
  1. 「ユークリッドは、背理法で素数が無数にあることを証明した」
  2. 「ユークリッドの証明は、存在のみを示しており、具体的な構成の手続きを示していない」
  3. 「ユークリッドは、最初のいくつかの素数の積に1を加えた数が素数であることを証明した」
このうちの3.は反例を示すことで容易に否定できる。番組では

２×３×５×７×11×13＋１＝59×509＝30031

という反例が紹介されていた。要するに、もしこの世界に存在する素数が２、３、５、７、11、13の6個しかないということが正しいとすると、それらのいずれでも素因数分解のできない数（30031）があることが示され、よって、素数が２、３、５、７、11、13の6個よりたくさんあることは証明できる。しかし、この「２×３×５×７×11×13＋１」という数がそれ以外の素数で素因数分解できるかどうかは全く検討されていない。仮に59×509という答えが見つからなかったとしても、素数であるという保証にはならない。

　余談だが、「素因数分解の一意性」（算術の基本定理）は「素数の積に分解される（素因数分解の存在）」という主張と「素因数分解があれば一意に決まる（分解の一意性）」という主張に分かれることがリンク先で説明されている。

　いずれにせよ、素数が無限にあることが分かっていても、より大きな素数を探索するということはきわめて困難な作業になるらしい。ウィキペディアの当該項目によれば、2013年12月現在で知られている最大の素数は、2013年1月に発見されたものであり、現在分かっている中で48番目のメルセンヌ素数：

257885161 −１

であり、十進法で表記したときの桁数は1742万5170桁に及ぶという。

ちなみに、ユークリッドの証明との関連で言えば、257885161−１ 以下の素数をすべて掛け合わせて１を加えたとしても、それが素数になるという保証はない。というか、もし素数であると確認されたなら、その数が新たに発見された史上最大の素数になるはずである。といって、この257885161−１ 以下の素数をすべて掛け合わせて１を加えた数がどういう合成数になるのか、すでに確認されているのかどうかは不明である。

　あと、またまた脱線するが、ユークリッドの証明に関しては、 といった興味深い話題がある。後者については、少し前に取り上げた、「できる保証」や、ｎ個の円のうちのどの2つをとっても、それぞれ2個の交点で交わるように円を配置できるという「できる保証」も関連してくる。

次回に続く。