![](https://blogimg.goo.ne.jp/user_image/13/65/87260d700de99e0adb7afbb87fac0845.jpg)
前回の記事に寄せられたコメントに、素数は”他人の介入を許さない孤高な数”とあった.つまり、素数と同じ孤高の数学者が憑かれるのも当然ではある。そんな私もどちらかと言えば、孤独の人間なので素数に惹かれるのだろう。
一方で、そんな魅惑的な素数ですが、13や17の様に悪魔的な側面を持つ。呪われた数とまでは言わないが、長年忌み嫌われ続けた負の歴史を持つ。
しかし、近年の盛んな素数の研究が素数を忌み嫌った人類と素数の間を取り持ってくれてるような気もする。
しかし、素数の研究が悪魔へ乗り口だとしたら?我々人類はネズミの様に素数を理解出来ないまま、死に絶えた方が平和なのだろうか?
それとも”周期ゼミ”の様に(難しい)素数を理解し、生存戦略に役立てた方が正しい選択なのだろうか?いや、旅やグルメやSNS三昧で安易な人生を送ってた方が・・・
前回は素数の基本の基を紹介しましたが、今回は素数の歴史と素数に憑かれた数学者達の物語です。
素数に憑かれた数学者たち(前半)
素数の歴史は素数に魅せられた数学者たちの歴史でもある。
素数の一番の疑問は、素数の出現が延々と続くのか?それともいつかは終りが来るのか?という事に尽きる。つまり、素数の出現確率はゼロに収束するのか?いや収束しないのか?
突き詰めれば、素数の個数は無限なのか?有限なのか?
ここで有名なのは、(以下に示す)紀元前300年頃の数学者であるユークリッドが著した「原論」による”素数は無限に存在する”事の証明である。2千年以上も前に記録されたものですが、この証明は数学的には十分ではない。
「原論」の第9巻に載ってる証明を忠実に訳せば、”a,b,…,k を任意に与えられた素数のリストとする。この時、p=a×b×⋯×kに1を加えた数p+1は素数であるか、合成数(素数の積)のいずれかである。
もし素数であれば、最初のリストに含まれない素数が得られた事になる。素数でなければ、何らかの素数pで割り切れるが、そのpは最初のリストには含まれない。なぜなら、リスト中の素数はpを割り切るので、p+1を割り切る事は不可能だからだ。故に、任意の素数のリストからリストに含まれない新たな素数が得られるので、素数は無数に存在する”とある。
一方で、この証明は一般的には、”素数の個数が有限と仮定し、p₁,…pₙが素数の全てとする。その積P=p₁×⋯×pₙに1を加えた数P+1は、p₁,…,pₙのいずれでも割り切れないので素数でなければならない。しかし、リスト以外の新たな素数が出現し、p₁,…,pₙが素数の全てだという仮定に反する。故に、仮定が誤りであり、素数は無限に存在する”事でよく知られている。
しかし、ユークリッドの証明は巷でよく言われる”背理法”ではなく、前者の様に直接証明の場合分けによるものである。しかし、2×3×5×7×11×13+1=59×509=30031(合成数)との反例により、前者の証明も後者の一般論も数学的に誤りである事が判る。
がしかし、こうした体系化された証明が2000年以上も前に記録された事自体が驚異的とも言えますね。
実は、”素数が無限個ある”事を最初に発見したのは、同じ紀元前のギリシャの数学者ピタゴラスであるとも言われている。
”数は万物である”と数を神として奉り、宗教の教祖でもあったピタゴラスは、ユークリッドよりも200年ほど前の人だから、素数に関する定理はピタゴラスの成果をまとめたものではないかと考えられている。
このピタゴラスの証明は、素数が無限個ある事だけでなく、無限個の素数を見つける方法も与えていた。
まず最初の素数2に1を足し、2+1=3という素数を得て、次に、2×3+1=7との素数を得る。ここで見つけた3つの素数の積に1を足し、2×3×7+1=43という新たな素数を得る。
更に、以上の4つの素数の積に1を加え、2×3×7×43+1=1807を得る。が、これは素数ではない。2,3,・・・で順に割っていけば、13で初めて割り切れるからだ。つまり、13という新たな素数が誕生する。
以上より、この手法を延々と繰り返せば、新たな素数がいくらでも見つかる筈だ。
故に、素数は無限個存在する事が示され、同時に素数の生成法も示される。
しかし、この手法は素数を見つける”実用的な方法”とは言えない。つまり、ピタゴラスの手法では素数の掛け算で巨大な数が出来、その約数である素数を見つけるのが現実的に困難であるからだ。
実際に、1990年代までは、この方法で43個までは素数を具体的に見つける事はできたが、44回目の掛け算が巨大過ぎる数となる為、その素数の約数を見つける事が出来なかった。因みに、44番目の素数が追加されたのは2010年の事で、68桁の素数であった。
但し、このピタゴラスの手法で全ての素数が見つかる事の証明は、未だに成されてはいない。
素数に憑かれた数学者たち(中盤)
ピタゴラスに負けず劣らず、ユークリッドは素数に関する様々な定理を発見しました。
特に、「素因数分解」の定理はとても重要で、”2以上の自然数は素数の積で一意的に表せる”という法則ですが、これは素数が原子のような役割を果たし、全ての物質が原子の組み合わせで作られてるのと同じ事を意味します。但し、原子が100個程度に対し、素数は無限に存在しますが・・・
更に、ユークリッドは約数と倍数の概念を発展させ、最大公約数と最小公約数を生み出します。前者は”aとbの共通の約数で最も大きな自然数”で、後者は”共通の倍数で最も小さな自然数”となります。
特に最大公約数はaとbの双方の素因数分解から求める事が出来ますが、大きな数の素因数分解となると困難になる。
しかし、ユークリッドが遺した「互除去」を使えば、素因数分解を使わずして(コンピュータを使ってだが)簡単に求める事ができる。
文字通り、互い違いに割って余りを出すアルゴリズムですが、126と98を例に取れば、まず128を98で割って余り(=28)を求める。次に98を余りの28で割り、その余りは14だから、更に28を14で割ると、余りは0になり、最後の除数(余り)14が最大公約数となる。
実際に素因数分解すると、126=2×3×3×7、98=2×2×7より、最大公約数は2×7=14となりますね。
この「ユークリッドの互除法」は、ひたすら”割って余りを出す”だけの計算だから、コンピュータを使えば、どんな大きい数も高速で最大公約数を弾き出せる。この事は、素数を使った暗号では重要な意味を持つ。
一方で、ユークリッドの後の世代で紀元前200年代に活躍したギリシャの数学者で、”ベータ”(第2のプラトン)と呼ばれたエラトステネスですが、本職は様々な研究施設を含むアレクサンドリア図書館の館長でした。
彼は地球を球体と考え、膨大な資料と経緯度を用いて自ら作成した地図を使い、2つの都市(アレキサンドリアとシエネ)での正午の太陽の位置と2都市間の距離から地球の周長を計算します。
これは、シエネと同経度のアレクサンドリアでの正午の太陽の影が作る角度は、地球上での緯度の差に等しく、両地点の距離が分かれば地球の大きさが求まるというもので、彼が弾き出した数値は実際の地球の周長に近い(17%の誤差)というから、ただただ驚くばかりですね。
そのエラトステネスが発見した「篩い(ふるい)」ですが、文字通り、自然数をふるいにかけ、素数だけを見つける手法です。
ピタゴラスの手法が実用的ではない事は先にも述べましたが、この「エラトステネスの篩い」では、ある程度の大きさの素数ならば、非常に効率的で有効なアルゴリズムとされる。
やり方は至って単純で、例えば、1から60までの自然数を縦10列・横6行に並べます(上図参照)。
まず2以外の2の倍数は全て素数ではないので、12,22,・・・,52を縦線で消し、1つ列を飛ばし、4,14,24,・・・,54を縦線で消す。以下同様に、6,16,・・・,56、8,18,・・・,58、10,20,・・・,60を縦線で消す。
次に、3以外の3の倍数も全て素数ではないので、12,21、6,15,24,33,42,51、9,18,27,36,45,54、30,39,48,57と規則的に並んでるので、斜め線で消す事ができる。
更に、5以外の5の倍数も全て素数ではないので、15,25,35,45,55を縦線で消す。
今度は7以外の7の倍数ですが、既に消されれるのを除けば49だけ消せばいい。
ここで√60=7.74・・・より、「前回」の”ルート判定法”を使えば、素数7の倍数を消した時点で残ってる数が全て素数となる事が判る。
このエラトステネスの篩いですが、倍数の位置が図形的な規則を持つ事から実行が容易という利点がある。
コンピュータが発明される以前は、このエラトステネスの手法やそれを改良した方法で素数表が作られていた。
こうした素数の解明の具体的な突破口を開いた「エラトステネスの篩い」ですが、オイラーはこの篩い法を解析学で表し、全ての素数に渡るオイラー積表示(オイラー積=ゼータ級数)を発見し、素数が無限個ある事の証明に繋げました(「リーマン2-10」参照)。更に、ディリクレを経由し、リーマンによりゼータ関数に大きく花開いたのは周知の事実である。
素数に憑かれた数学者たち(後半)
ピタゴラスやユークリッド、それにプラトンやエラトステネスと数々の天才数学者を生み続けたギリシャ時代以降、素数に対する興味は薄れていく。しかし、17世紀のフランスの数学者であるフェルマーが素数を復活させます。
フェルマーと言えば、私もブログにした”フェルマーの定理”が有名で、整数に関する数々の発見は現代の整数論に繋がる強い影響力を与えました。
例えば、フェルマーの「素因数分解法」では、x²−y²=(x+y)(x−y)の簡単な因数分解の公式を使って、素因数分解したい数を平方数の引き算で表す事を思いつきます。つまり、ある数を平方数の引き算で表せれば、和と差の積に分解できる。
例えば、9991が素数か否かを調べる時、この数は3,5,7,11など小さな素数では割り切れない。そこで、9991=100²−3²=(100+3)(100−3)=103×97と素因数分解出来るので、2つの素数103と97が求まる。
但し、この方法論では素因数分解したい数が平方数の引き算でピタリと表される時だけでなく、素因数分解したい数が平方数の引き算を割り切る時にも(運が良ければだが)上手く行く。
例えば、1517が素数となるかを調べる時は、この数が割り切る平方数の引き算を試行錯誤で見つける必要がある。
事実、1517は48991(=700²−3²)を割り切り、48991÷1517=323となる。が、どうやって48991を見つけるのか?
これは実際には”数体ふるい法”や量子コンピュータなど特殊な方法を使わないと見つからない。
まず、48991は=(700+3)(700−3)=703×697と分解できるから、1517は703×697を割り切る。そこで仮に、1517が素数でないとしてpを約数に持つとすれば、pは703か697かどちらかを割り切る筈。そしてもし、pが703を割り切るなら、pは1517と703の公約数となる。
ここで、この2数にユークリッドの互除法を適用し、pを求める。1517÷703は商が2で余りが111、703÷111は商が6で余りが37、111÷37=3(余り0)となり、最後の余りである37が最大公約数となる。
故に、1517の約数p=37が見つかり、1517=37×41と素因数分解できる。
つまり、1517が平方数の引き算で表されなくとも、ある平方数の引き算(ここでは48991)を割り切る事ができれば、(運良くだが)素因数分解ができ、新たな素数が見つかる。
少し長くなったので、今日はここまでです。
ピタゴラスやユークリッドの素数に関する数々の発見や証明も見事ですが、エラトステネスの篩(ふるい)には脱帽の感がありますね。
次回は、フェルマーの素数に関する一連の発見とそのフェルマーの研究を受け継いだオイラーの偉業について書きたいと思います。
古代ギリシャ時代から引き継がれてきた素数の神秘ですが、紀元前1600年頃の古代エジプト第2中間期にて、素数の初等的な性質が部分的に知られてた事がパピルスなどの資料で示唆されている。これは、古代バビロニア時代に既に60進法が使われてた事からすると、当然とも言える。
まさに数学が誕生する前に、素数は既に研究されていた。
![](https://blogimg.goo.ne.jp/user_image/60/09/b8265b940727e4f1c5d034495a416f6c.png)
25,35,55と49が消えてないような
間違ってたらゴメンナサイです。
ありがとうございます。
早速、修正します。
思わずウッカリしていました。
本当に助かりますです。
とわかったようなことを書いていますが、すべて転象さんの記事から刺激を受けて偉そうに書いてみただけです。
またいろいろ教えてください。
素数となると、憑かれちゃうんですよね。
それでいて最後には心身ともに疲れてしまう(笑)。
言われる通り、私達は日頃随分つまらぬ事に忙殺されすぎてる。勿論、詰まらないから基になるんでしょうが
その点、素数の神秘は永遠の課題であり、その答えを求める度に色んな発見がある。
結局は人それぞれなんですかね。
コメントいつもありがとうございます。
その他、わずかな誤差で、地球の周囲を算出するなど、すごい人!
呼称「ベータ」には、「プラトン=アルファになれなかった男」という意味もあるそうですが、掘り下げてみると、いろいろな発見、気づきを与えてくれそうです。
考えてみると、人間の思考回路って、エラトステネスの頃とほとんど変わってないんですよね。
多少のヴァージョンアップはしていますが、同じ所をぐるぐる回っている気がします。
AIは人間の知能を越えた時、新しいパラダイムが生まれるかもしれません。
エラトステネスはベータどころか、アルファをも凌ぐとても凄い人だったんですよね。
彼がいたから、オイラー積が発見され、リーマンのゼータ関数に継承され、難関不落のリーマン予想があります。
人類の思考回路は古代ギリシャ時代、いや古代バビロニア時代から変わってないのかもです。
今の時代にエラトステネスがいたら、自民党なんか篩(ふるい)にかけられて、捨てられてたでしょうね。
でも、色んな考え方があるんですよね。人類には。
だから、素数は神秘的だし、人間は面白い。
コメントいつも勉強になります。
とも言い換えれるが、Pが合成数の時は素数で割り切れるので、”Pはどの素数で割っても余りが1となる”事自体が間違っている。
つまり、仮定の以前の前提で破綻してるので、どう転んでも背理法としては成り立たない。
一方で、ユークリッドはPが素数か合成数かの時に分け、直接法を用いて矛盾を示したつもりだが、これも”Pはどの素数で割っても余りが1となる”と決めつけてる時点で、この証明は破綻している。
つまり、事実と異なる前提がある矛盾が成り立ち、背理法として成立してるような誤解を受ける。これも美しく見える論理のトリックと言える。
ではなく
事実と異なる前提が矛盾を成り立たせ
でした。
言われる通り
”Pはどの素数で割っても余りが1となる”との前提に誤りがある訳で・・・
確かに、2,3,5,7,11,13を全ての素数と仮定すれば、それら全ての素数の積に1を足せば、59×509=30031(合成数)となり、新たに59と509の素数が誕生するので、条件付きの直接法としては間違ってはいないんですが、背理法としてみれば、前提が間違ってるので、数学的には間違ってるとなります。
こういう所が数学における論理の罠とも言えるんでしょうが、ユークリッドもあまりに美しいシンプルな論理にうっとりしたんでしょうか。
特に、p+1が素数の時は新たな素数が現れるとありますが、p+1が素数になるのは少なく、合成数になることの方がずっと多い。
故に、新たな素数が現れるとしても全ての素数を網羅する保証はどこにもない。
むしろ、合成数の時の方が素因数分解により、より多くの新たな素数が現れる。それでも全ての素数を網羅出来る保証はない。
つまり、”全ての素数のリスト”という仮定で見ても無理があるし、直接的いや直感的すぎて十分ではない。
一見、論理的に見て正しいと思える証明も、直感によるワナに嵌りやすいという典型の例(トラップ)でしょうか。