素数の基本を理解しよう”その２”(更新)〜素数に憑かれた偉人たち

　前回の記事に寄せられたコメントに､素数は”他人の介入を許さない孤高な数”とあった．つまり､素数と同じ孤高の数学者が憑かれるのも当然ではある。そんな私もどちらかと言えば､孤独の人間なので素数に惹かれるのだろう。
　一方で､そんな魅惑的な素数ですが､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進法が使われてた事からすると､当然とも言える。
　まさに数学が誕生する前に､素数は既に研究されていた。