完全数　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　

　ある数の約数（但し、自分自身は除く）の総和がある数自身に等しいとき、その数のこと
を、完全数という。

　完全数で一番有名な数は、６ である。

実際に、６ の約数は、１、２、３ なので、１＋２＋３＝６ が成り立っている。

　６ という数は、神（１）・男（２）・女（３）を含む「世界」を表現しているので、完全数と呼ばれ
たらしい。

　完全数は、６ 以外に、２８、４９６、８１２８、３３５５０３３６、．．．などが知られている。


　ｙｔｋさんからのコメントです。（平成２７年３月１５日付け）

　全然関係ないですが、ISO（国際標準化機構）の規格の一つに「性別コード」（ISO 5218）と
いうものがあって、

0 = not known（不明）、1 = male（男性）、2 = female（女性）、9 = not applicable（該当なし）

という国際基準。「該当なし」を入れているあたり、性的少数者にも配慮できていて好ましい
のかなと。ところで、婚約数は現在発見されている限りではすべて奇数と偶数なのですが、
どちらが男女でどちらが女性というのは決まっているのだろうか？


（追記）　Ｗｅｂサイト「数の不思議世界」、平成２５年９月１９日付けの飯高　茂先生の書き
　　　　込みに興味を持った。サイトの読者からの情報とのことです。

　約数の和を σ と書くとき、σ(a)＝２ａ　が完全数の定義ですが、σ(a)＝２ａ−１　を概完
全数といい、これは２のべきだけだろうという予想があるそうです。

　また、σ(a)＝２ａ＋１　を擬完全数といい、これの存在は知られていないそうです。

例　ａ＝２^ｎ の約数は、　１、２、２²、２³、・・・、２^ｎ なので、

　σ(a)＝１＋２＋２²＋２³＋・・・＋２^ｎ＝２^ｎ+1−１＝２・２^ｎ−１＝２ａ−１

　よって、ａ＝２^ｎ は、概完全数であると言える。


　さて、完全数を求める面白い方法があることを最近知ったので、ここで、まとめておきたい。

　１ばかり並べた２進数を、メルセンヌ数という。

　１１、１１１、１１１１、１１１１１、１１１１１１、１１１１１１１、．．．　

　これらを、十進数に直せば、次のようである。

　　　　　１１＝１・２＋１＝３＝２²−１
　　　　１１１＝１・２²＋１・２＋１＝７＝２³−１
　　　１１１１＝１・２³＋１・２²＋１・２＋１＝１５＝２⁴−１
　　１１１１１＝１・２⁴＋１・２³＋１・２²＋１・２＋１＝３１＝２⁵−１
　１１１１１１＝１・２⁵＋１・２⁴＋１・２³＋１・２²＋１・２＋１＝６３＝２⁶−１
１１１１１１１＝１・２⁶＋１・２⁵＋１・２⁴＋１・２³＋１・２²＋１・２＋１＝１２７＝２⁷−１
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　メルセンヌ数は、一般に、Ｍ_n＝２ⁿ−１ の形で知られている。

　見て分かるように、メルセンヌ数には素数であるものと、そうでないものが混在している。

　ｎ が合成数のとき、明らかに、Ｍ_ｎ は素数になりえない。Ｍ_ｎ が素数となるためには、ｎ
が素数であることが必要条件である。


（追記）　令和５年５月１７日付け

　上記の「Ｍ_ｎ が素数　ならば、ｎ は素数である」ことを示せという問題が、
一橋大学後期（２０２０）で出題された。有名問題であるが、丁寧な導入もあり、取り組みやす
いだろう。

第１問　ａ、ｂを正の整数とする。

（１）　ａ が ｂ の倍数ならば、２^a−１は、２^ｂ−１の倍数であることを示せ。
（２）　２^ａ−１ が素数ならば、ａ は素数であることを示せ。
（３）　２^ａ−１＝（２ａ＋１）（８ａ＋１） を満たす ａ を求めよ.

（解）（１）　題意より、ａ＝ｂｋ　（ｋは自然数）　とおける。このとき、

　２^a−１＝（２^ｂ）^ｋ−１＝（２^ｂ−１）（（２^ｂ）^ｋ-1＋（２^ｂ）^ｋ-2＋・・・＋１）

と書けるので、２^a−１は、２^ｂ−１の倍数である。

（２）　証明は背理法による。ａ は素数でないと仮定すると、ａ＝１　または　ａ は合成数

　ａ＝１　のとき、　２^a−１＝１　は素数でない。これは、２^ａ−１ が素数であることに矛盾

　ａ が合成数とすると、ａ＝ｂｋ　（ｂ、ｋは２以上の自然数）　と書ける。このとき、（１）より

　２^a−１は、２^ｂ−１（≧３）の倍数となり、２^a−１＞２^ｂ−１　より、

　２^ａ−１ が素数であることに矛盾

　以上から、何れにしても矛盾が導かれるので、ａ は素数でないと仮定したことが誤りである。

したがって、　２^ａ−１ が素数ならば、ａ は素数である。

（３）　２^ａ−１＝（２ａ＋１）（８ａ＋１）＝１６ａ²＋１０ａ＋１　より、　２^ａ-1＝８ａ²＋５ａ＋１

　　

　グラフより、ａ＝１１のとき、２^ａ-1＝８ａ²＋５ａ＋１　を満たす。

　実際に、　２^ａ-1＝２¹⁰＝１０２４　、８ａ²＋５ａ＋１＝９６８＋５５＋１＝１０２４　から
成り立つ。　　（終）


　特に、メルセンヌ数が素数となる場合、それは、メルセンヌ素数といわれる。
（メルセンヌ素数を、単に、メルセンヌ数という場合もある。）

　メルセンヌ素数は、まだそれほど数多く（３１個位？）は知られていない。

　その数が素数かどうかを判定することは、一般に大変であるが、Ｌｕｃａｓは、次の非常に
能率的なＬｕｃａｓの定理（ルカステスト）を発見し、その労力は大幅に緩和された。

Ｌｕｃａｓの定理（１８７６年）

　数列｛ａ_ｎ｝を、ａ₁＝４、ａ_ｎ＋１＝ａ_ｎ²−２　により定義する。
　　　　４，１４，１９４，３７６３４，１４１６３１７９５４，・・・
このとき、Ｍ_ｎ （ｎ は３以上の素数）が素数であるための必要十分条件は、
ａ_ｎ−１ がＭ_ｎ で割り切れることである。

例　ａ₂÷Ｍ₃＝１４÷７＝２ で割り切れる。よって、Ｍ₃ はメルセンヌ素数である。

　　ａ₄÷Ｍ₅＝３７６３４÷３１＝１２１４ で割り切れる。

　　　よって、Ｍ₅ はメルセンヌ素数である。

　上の例では、実際に、ａ₂、Ｍ₃ などの値を求めて、割り算を実行したが、その方法は、あ
まり実戦的ではない。次のように計算するのが普通らしい。

　Ｍ₅＝３１ に注意して、

　ａ₁＝４　、ａ₂＝１６−２＝１４　、ａ₃＝１４²−２＝１９６−２＝１９４≡８　（ｍｏｄ　３１）
　ａ₄≡６４−２＝６２≡０　（ｍｏｄ　３１）

　よって、ａ₄ が、Ｍ₅ で割り切れるので、Ｌｕｃａｓの定理より、Ｍ₅ はメルセンヌ素数である。

　メルセンヌ素数を用いると、完全数は簡単に作られる。

定理(Euclid)　　Ｍ_ｎ をメルセンヌ素数とすれば、Ｍ_ｎ（Ｍ_ｎ＋１）/２ は完全数である。

（証明）　Ｍ_ｎ＝２ⁿ−１ より、

　　Ｍ_ｎ（Ｍ_ｎ＋１）/２＝（２ⁿ−１）・２ⁿ/２＝（２ⁿ−１）・２^ｎ−1 である。

この約数の総和は、２ⁿ−１ が素数であることに注意して、

　　（１＋２＋２²＋・・・＋２^ｎ−１）（１＋２ⁿ−１）＝（２ⁿ−１）・２^ｎ

　ここで、　Ｓ＝１＋２＋・・・・・・＋２^ｎ-1　とおくと、２Ｓ＝　　２＋２²＋・・・＋２^ｎ-1＋２^ｎ　より、

　Ｓ＝２^ｎ−１　である。（詳しくは、「約数の個数と和」を参照）

この和から、自分自身を差し引けば、

　（２ⁿ−１）・２^ｎ−（２ⁿ−１）・２^ｎ−1＝（２ⁿ−１）・２^ｎ−1・（２−１）＝（２ⁿ−１）・２^ｎ−1

となって、自分自身と一致する。

したがって、Ｍ_ｎ（Ｍ_ｎ＋１）/２ は、完全数である。（証終）

（注）この事実は、既にユークリッド原論で示されていることらしい。ギリシャ時代に完全数
　　は　６、２８、４９６、８１２８ の４個が知られていたようだ。

例　冒頭であげた完全数は、次のようにして求められる。
　　Ｍ₂＝３　より、３・（３＋１）/２＝６
　　Ｍ₃＝７　より、７・（７＋１）/２＝２８
　　Ｍ₅＝３１　より、３１・（３１＋１）/２＝４９６

　したがって、４９６の次の完全数も容易に求められる。

　　Ｍ₇＝１２７　より、１２７・（１２７＋１）/２＝８１２８

　Ｅｕｌｅｒ によれば、偶数の完全数は必ずこの方法で求められるようだ。

　ところで、奇数の完全数が存在するかどうかは、まだ分かっていないようだ。

（参考文献：小島寛之　著　数学の遺伝子（日本実業出版社）
　　　　　　　　和田秀男　著　数の世界　整数論への道（岩波書店）
　　　　　　　　Ｍ．ラインズ　著　片山孝次　訳　数　その意外な表情（岩波書店））


（追記）　広島工業大学の大川研究室から情報をいただいた。

　２００２年６月９日現在、３９個のメルセンヌ素数が発見されている。従って、完全数も３９個
あることになる。

　最大のメルセンヌ素数は、現在、２^13466917−１で、４，０５３，４９６桁の数である。

　これらは、スーパーパソコンを用いて計算したのではなく、世界中の２０万台以上のパソコ
ンが参加して発見されたとのことである。「すごい！」の一語である。


（追記）　２００３年１２月３日、過去最大の素数が発見された（検証により、確認）。

　２^20996011−１　６３２万４３０桁の数で、４０番目のメルセンヌ数だという。

　ミシガン州立大学の大学院生マイケル・シェイファー（Ｍｉｃｈａｅｌ　Ｓｈａｆｅｒ）さんが中心となっ
て、世界中の２００万台を越えるパソコンを結んで、２年がかりの計算で発見されたとのこと
である。


（追記）　２００４年５月１５日、過去最大の素数が発見された（検証により、確認）。

　２^24036583−１　７２３万５７３３桁の数で、４１番目のメルセンヌ数だという。


（追記）　２００５年２月２７日、過去最大の素数が発見された（検証により、確認）。

　２^25964951−１　７８１万６２３０桁の数で、４２番目のメルセンヌ数だという。


（追記）　２００５年１２月１５日、過去最大の素数が発見された（検証により、確認）。

　２^30402457−１　９１５万２０５２桁の数で、４３番目のメルセンヌ数なのかな？


（追記）　２００６年９月４日、過去最大の素数が発見された（検証により、確認）。

　２^32582657−１　９８０万８３５８桁の数で、４４番目のメルセンヌ数なのかな？


（追記）　２００８年８月２３日、過去最大の素数が発見された（検証により、確認）。

　２^43112609−１　１２９７万８１８９桁の数で、４７番目のメルセンヌ数なのかな？
発見者は、Edson　Smith


（追記）　２００８年９月６日、過去最大の素数が発見された（検証により、確認）。

　２^37156667−１　１１１８万５２７２桁の数で、４５番目のメルセンヌ数なのかな？


（追記）　２００９年４月１２日、過去最大の素数が発見された（検証により、確認）。

　２^42643801−１　１２８３万７０６４桁の数で、４６番目のメルセンヌ数なのかな？
発見者は、Odd　Ｍ．Strindmo


（追記）　２０１３年１月２５日、過去最大の素数が発見された（検証により、確認）。

　２^57885161−１　１７４２万５１７０桁の数だという。４８番目のメルセンヌ数なのかな？

　米国・セントラルミズーリ大学の研究者が見つけたと、世界各地のボランティアのコンピュ
ータをつないで素数探しをするプロジェクト、ＧＩＭＰＳが発表した。
（２０１３年２月７日付け朝日新聞夕刊）


（追記）　２０１６年１月２１日、過去最大の素数が発見された（検証により、確認）。

　２^74207281−１　（３００３７６４１８０・・・・・・・１０８６４３６３５１）

　２２３３万８６１８桁の数だという。４９番目のメルセンヌ数なのかな？

　Ａ４判の紙にびっしり印刷しても約１万枚必要とのことで、その膨大な量に圧倒される。

　米国・セントラルミズーリ大学は、過去最大の素数をクーパー教授が見つけたと、１月２１
日、発表した。クーパー教授は、世界各地のボランティアのコンピュータをつないで素数探し
をするプロジェクト「ＧＩＭＰＳ」のメンバー。

　２０１５年９月１７日にコンピュータは新たな素数を見つけていたが、発見に気付いたのは、
２０１６年１月７日であったという。（２０１６年１月２４日付け朝日新聞夕刊）


（追記）　２０１７年１２月２６日、過去最大の素数が発見されたようだ。

　２^77232917−１　十進法では、２３２４万９４２５ 桁の数だという。
発見者は、Jon　Pace


（追記）　２０１８年１２月、過去最大の素数が発見されたようだ。

　２^82589933−１　十進法では、２４８６万２０４８ 桁の数だという。

　メルセンヌ素数についての最新情報


（追記）　平成１９年１２月２０日付け

　メルセンヌ数 Ｍ_ｎ の ｎ の部分を一覧にすると、下記のようになる。
（参考：「メルセンヌ素数について」）

　？のものは、まだ何番目かが確定していないらしい。（発見者は上記ＨＰを参照）

　４１番目のメルセンヌ数は、２００４年に発見された。７２３万５７８３桁と聞いても、あまり
ピンとこないが、１桁当たり４ｍｍの文字の幅（今、この文章を書いている文字の幅！）と
して、１直線にすべて書き並べると、その長さは、

　７２３５７８３×４÷１０÷１００÷１０００＝２８．９４３１３２　（ｋｍ）

から、およそ ２９ ｋｍ ほどにもなる。

　この距離は、東京都中央区日本橋から第一京浜国道に沿って、ちょうど横浜市神奈川
区までにほぼ等しい。（大体の長さの感覚が掴めたかな？）

（コメント）　１ｋｍ３分の人が走っても、１時間２７分もかかる（！）し、普通に歩いて（分速
　　　　　　８０ｍ）も６時間くらいかかる距離ですね。非常に長い数の並びということがイメ
　　　　　　ージできます。

（追記）　平成２１年５月９日付け

　ゴールデンウィーク中、あまり晴天に恵まれなかったが、今日は久しぶりの好天が望め
そうである。当ＨＰがいつもお世話になっているＨＮ「ｚｋ４３」さんから、次のような事実を
ご教示いただいた。

　６以外の完全数は、１から始まる連続する奇数の立方和で表せる

　例えば、

　２８＝１³＋３³（＝１＋２７）　、４９６＝１³＋３³＋５³＋７³（＝１＋２７＋１２５＋３４３）

　８１２８＝１³＋３³＋５³＋７³＋９³＋１１³＋１３³＋１５³
　　　　（＝１＋２７＋１２５＋３４３＋７２９＋１３３１＋２１９７＋３３７５）

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　（う〜む、なるほど！）

　ｚｋ４３さんによれば、

１³＋３³＋５³＋・・・＋（２ｎ−１）³



において、　　とすると、右辺が　２^ｐ-1（２^ｐ−１）　となり、これは、メルセンヌ数

Ｍ_ｐ＝２^ｐ−１　に対して、Ｍ_ｐ（Ｍ_ｐ＋１）/２＝２^ｐ−１（２^ｐ−１） が完全数であることから

　６以外の偶数の完全数は、必ず、１から始まる連続する奇数の立方和で表せる

ことが示された。

（コメント）　奇数の完全数の存在は、まだ不明だが、奇数の完全数についてはどうなんで
　　　　　　しょうかね？

　８１２８ の次の完全数は、Ｍ₁₃＝２¹³−１＝８１９１　（１４５６年　発見者不明）を用いて、

　　８１９１×８１９２÷２＝３３５５０３３６

である。

　理論的には明白だが、具体的に確かめてみよう。

　３３５５０３３６＝２¹²・８１９１　なので、約数は全部で、（１２＋１）（１＋１）＝２６（個）

あり、その約数は、

　１、２、４、８、１６、３２、６４、１２８、２５６、５１２、１０２４、２０４８、４０９６、

　８１９１、１６３８２、３２７６４、６５５２８、１３１０５６、２６２１１２、５２４２２４、１０４８４４８、

　２０９６８９６、４１９３７９２、８３８７５８４、１６７７５１６８、３３５５０３３６

で、その総和は、　６７１００６７２　で、　６７１００６７２÷２＝３３５５０３３６　より、確かに

３３５５０３３６　は完全数である。

　このとき、ｚｋ４３さんの解法の指針に従えば、ｎ＝２⁶＝６４　なので、

　　３３５５０３３６＝１³＋３³＋５³＋・・・＋１２７³

と書けることが分かる。

（コメント）　とても面白い性質ですね！ｚｋ４３さんに感謝します。

　また、Ｓ（Ｈ）さんからの情報によれば、偶数の完全数には次の性質もあるそうだ。

　　偶数の完全数は、三角数である

　証明は易しい。

　偶数の完全数は、素数 ｐ を用いて、２^ｐ−１（２^ｐ−１） と表せる（Ｅｕｌｅｒ）ので、

　　２^ｐ−１（２^ｐ−１）＝２^ｐ（２^ｐ−１）/２＝１＋２＋３＋・・・＋（２^ｐ−１）

より明らかだろう。

　さらに、

　　偶数の完全数の末尾は、必ず、６ または ８ である

という事実も興味深い。

　これは、２より大きい素数が、４ｎ＋１型か、４ｎ＋３型の何れかであることから簡単に示
される。

　実際に、　ｐ＝４ｎ＋１　（ｎ は自然数）　のとき、

　　２^ｐ−１（２^ｐ−１）＝１６^ｎ（２・１６^ｎ−１）

　　ここで、　１６^ｎ＝（１０＋６）^ｎ≡６^ｎ≡６　（ｍｏｄ　１０）　なので、

　　２^ｐ−１（２^ｐ−１）＝１６^ｎ（２・１６^ｎ−１）≡６（２・６−１）≡６　（ｍｏｄ　１０）

　同様にして、　ｐ＝４ｎ＋３　（ｎ は自然数）　のとき、

　　２^ｐ−１（２^ｐ−１）＝４・１６^ｎ（８・１６^ｎ−１）

　　ここで、　１６^ｎ＝（１０＋６）^ｎ≡６^ｎ≡６　（ｍｏｄ　１０）　なので、

　　２^ｐ−１（２^ｐ−１）＝４・１６^ｎ（８・１６^ｎ−１）≡４・６（８・６−１）≡４・７≡８　（ｍｏｄ　１０）

である。　ｐ＝２　のときの完全数は６なので、もちろん命題は成り立っている！

（コメント）　Ｓ（Ｈ）さんの情報検索はスゴイですね！いつも感謝しています。

　奇数の完全数の存在は、まだ不明らしいが、奇数の完全数に関して、ｚｋ４３さんより情報
をいただいた。（平成２１年５月１３日付け）

　素因数の種類が２種類の奇数は完全数ではない

（証明）　Ｎ＝ｐ^ｍ・ｑ^ｎ　（ｐ、ｑ は奇素数で、ｐ＜ｑ、ｍ、ｎ は自然数）とする。

　このとき、Ｎの正の約数の総和 Ｓ は、

　Ｓ＝（１＋ｐ＋ｐ²＋・・・＋ｐ^ｍ）（１＋ｑ＋ｑ²＋・・・＋ｑ^ｎ）

　そこで、

Ｓ/Ｎ＝（１/ｐ^ｍ＋１/ｐ^ｍ-1＋・・・＋１/ｐ＋１）（１/ｑ^ｎ＋１/ｑ^ｎ-1＋・・・＋１/ｑ＋１）

　　＜（１＋１/ｐ＋１/ｐ²＋・・・＋１/ｐ^ｍ＋・・・）（１＋１/ｑ＋１/ｑ²＋・・・＋１/ｑ^ｎ＋・・・）

　　≦（１＋１/３＋１/３²＋・・・＋１/３^ｍ＋・・・）（１＋１/５＋１/５²＋・・・＋１/５^ｎ＋・・・）

よって、　Ｓ/Ｎ＜｛１/（１−１/３）｝・｛１/（１−１/５）｝＝１５/８＜２

　もし、Ｎが完全数ならば、　Ｓ＝２Ｎ　でなければならないので、このことから、

　素因数の種類が２種類の奇数は完全数にはなり得ない

ことが示された。　　（証終）


（コメント）　ｚｋ４３さん、ありがとうございます。奇数の完全数って、本当に存在するのでしょ
　　　　　　うか？


　当ＨＰの掲示板「出会いの泉」に、当ＨＰがいつもお世話になっているＨＮ「ＧＡＩ」さんが、平
成２５年１月２７日付けで、次のような書き込みをされた。

　「２ⁿ−１が素数なら、（２ⁿ−１）・２^n-1は完全数である」というユークリッド時代から知られて
いたことから、２ⁿ−１がいつ素数になるかが問われ、ｎが合成数なら必ず因数分解されてし
まうので、ｎは素数ｐについて調べられていった。

　メルセンヌは１６４９年の手紙の中で、

　ｐ＝2、3、5、7、13、17、19、31、67、127、257 のとき、２ⁿ−１が素数（メルセンヌ素数）

であると証明抜きで発表したとある。（もちろん高性能のコンピュータは存在しない。）

　現在、これらが素数になれるものがコンピュータの道具も使って、

　ｐ＝2、3、5、7、13、17、19、31、61、89、107、127、521、607、…、13466917

　(→　参照：「A000043」)

と現在まで39個見つかっているという。従って、メルセンヌは、ｐ＝61を見過ごし、67、257を
誤って判断したことになる。

　そこで、メルセンヌが間違った ｐ＝67について、２⁶⁷−１の因数分解は？に興味が湧いた。

　原理的には、「floor(sqrt(2^67-1))=12148001999」より、1〜12148001999 までに現れるす
べての素数でことごとく割っていけば目的が達成できるが、この中の素数は余りにも多すぎ
る。（547932122個もある。）

　そこで、コンピュータがない時代にメルセンヌが判断を間違えないようにするためには、こ
の因数分解をどの様に行えばよいかのアイデアを教えて下さい。


　当ＨＰがいつもお世話になっているＨＮ「空舟」さんからのコメントです。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２５年１月２７日付け）

　Ｗｅｂサイト「フェルマー素数について」によると、１８８０年、ランドリーは（８２才という高齢にも
かかわらず）、２⁶⁴＋１ の素因数分解が

　　Ｆ₆＝２７４１７７×６７２８０４２１３１０７２１

となることを示しました。でもどうやって見つけたのかは書かれていませんでした。こちらを
考察してみました。

　２⁶⁴＋１≡0　(ｍｏｄ　ｐ) とおくと、URLにも有るように、ｐ＝１２８N＋１型です。

　ｐ＝１２８N＋１、ｑ＝１２８M＋１、ｐｑ＝２⁶⁴＋１ とおくと、M＝(２⁵⁷−N)/(１２８N＋１)

M＝(２⁵⁷−N)/(１２８N＋１)が割り切れる必要条件を調べればNを絞れるかもしれないと思っ
たのですが、なかなか考察が進めないです。[実際の答えは、N=4284、M=525628291490]

　同様に、２⁶⁷−１＝(６７N＋１)(６７M＋１) とおくと、式 M＝(A−N)/(６７N＋１) を得ます。
（ここで A＝２・(２⁶⁶−１)/６７＝2202596307308603178）

　ここで、M、Nは明らかに偶数なので、M＝2m、N＝2n、A＝2a　とおいても良いですね。

　m＝(a−n)/(134n＋１)　、a＝(２⁶⁶−１)/６７＝1101298153654301589

　[実際の答えは、 n＝1445580、 m＝5685360129]


　ＧＡＩ さんからのコメントです。（平成２５年１月２７日付け）

　上記のアイデア（フェルマーの小定理の活用？）から探すべき素数は、ｐ＝１３４ｋ＋１型
に限って調べればよい。（だいぶ絞れることにはなるが・・・）

　そこで、PARIという計算ソフトでこっそり調査してみました。

? for(k=1,1450000,if(isprime(134*k+1)==1,if(component(Mod(2^67-1,134*k+1),2)==0,print(k,";",134*k+1))))

で実行したら、「1445580　、193707721」の結果がヒットしました。これから、

　２⁶⁷−１＝193707721×761838257287

と分解でき、合成数であることが確認できました。しかし、これを当時手計算で達成できるも
のだろうか？不思議はさらに深まりました。


（追記）　ＧＡＩ さんが、メルセンヌ数の歴史を調べられた。（平成２７年３月１４日付け）

　ｐを奇素数とするとき、M(ｐ)＝２^ｐ−１　(メルセンヌ数）が素数になるのか？まあ、

ｐ＝３　--> M(3)=2^3-1=7             :prime
ｐ＝５　--> M(5)=2^5-1=31            :prime
ｐ＝７　--> M(7)=2^7-1=127           :prime
ｐ＝１１　--> M(11)=2^11-1=2047         ?（実は23*89に分解可能）
ｐ＝１３　--> M(13)=2^13-1=8189         ?
ｐ＝１７　--> M(17)=2^17-1=131071       ?
ｐ＝１９　--> M(19)=2^19-1=524287       ?
　　･･･・・・
ｐ＝６７　--> M(67)=2^67-1=147573952589676412927
　　･･･・・・
ｐ＝１２７　--> M(127)=2^127-1=170141183460469231731687303715884105727
　　･･･・・・
ｐ＝２５７　--> M(257)=2^257-1
　　　　　　　　=231584178474632390847141970017375815706539969331281128078915168015826259279871

　これに対し、メルセンヌは、１６４４年に、

　　ｐ＝2、3、5、7、13、19、31、67、127、257　だけが素数になる

と予想した。
（この予想は誰もこんな大きな数では確認出来ないだろうと高をくくったある意味ハッタリ）
＜後日p=67は間違いで、また、61、89、107　が抜け落ちていることが判明する。＞

　しかし、この予想に果敢にも挑戦した人が現れ、１８７６年エドアール・リュカが１９年の歳月
をかけて、M(127)が素数であることを確認したという。

　その方法は、ｐが、ｐ≡3 (mod 4) である素数のとき、

　　S(0)=3、S(n)=S(n-1)²-2　 (n=1、2、3、･･･）

と定義するとき、S(p-2)がM(p)で割り切れれば、M(p)は素数であるというものである。

　実際、ｐ＝７、１１ で確認してみると、

S(0)=3　、S(1)=S(0)^2-2=3^2-2=7　、S(2)=S(1)^2-2=7^2-2=47　、S(3)=S(2)^2-2=47^2-2=2207
S(4)=S(3)^2-2=2207^2-2=4870847　、S(5)=S(4)^2-2=4870847^2-2=23725150497407
S(6)=23725150497407^2-2=562882766124611619513723647
S(7)=562882766124611619513723647^2-2=316837008400094222150776738483768236006420971486980607
以下
S(8)=1003856898919213766887542399928262567048796276831819015150993986
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　13465618884806971304035121947368905594088447
S(9)=1007728673507700566098200806106507306807447530046601244462938848757476965211565176350
　　　00261283676793017447903659202787756017660002174559979308093950457876685360362550516268
　　　2177708433023235042368022152858871807

　これらの数に対し、

　　S(5)/M(7)=23725150497407/127=186812208641（ピタリ割り切れる）

　しかし、S(9)/M(11)の計算は余りが1034となり割り切らない。つまり、M(7)=127は素数で、
M(11)=2047は合成数であると主張する。

　この原則に則って、リュカは１９年という歳月をかけて、M(127)の素数性を示した。
（手計算で素数を確認された最大の記録であることは未だに破られていない。）

　この判定を用いると、実は、M(67)も合成数であることが判るという。しかし、どのような分
解になるのかはリュカの方法では出てこない。

　これに対し、１９０３年コロンビア大学数学教授フランク・ネルソン・コールが夕食後の一時
を３年計算し続けて、M(67)=193707721*761838257287 を見つけたという。

　数学者の素質として本当に粘り強い気質、倦まず弛まず歩き続ける忍耐力が必要な条件
であることをしみじみ教えてくれます。素数で片端から割っていくという方法からリュカのある
意味単純作業の繰り返しによる素数判定という新たな道が開けたことの意味は大きい。しか
し、それでも莫大な数字に膨れていくことは難点でもある。

　これに対し、１９３０年デリック・ヘンリー・レーマーがリュカの方法に画期的な改良を加え、
M(257)が合成数であることを証明する。（この経緯は次回に．．．）


　ＧＡＩ さんからの続報です。（平成２７年３月１５日付け）

　さて、リュカによる素数判定テストを受けて、デリック・ヘンリー・レーマーは（この人の父は
２０世紀の初めには10017000までの素数表を作成したという。）、子供心に父の背中を見て
育ったんでしょう、彼が25歳の時リュカの素数判定を劇的に効率化させる方法を編み出した。

　それが、数列S(n)を、　S(1)=4、S(n+1)=S(n)-2 (mod M(p)) :M(p)=2^p-1 (p:prime)

で定義しておけば、　S(p-1)≡0 (mod M(p))　⇔　M(p)は素数

　ここに、modの世界で処理するところに画期的な進歩をもたらす。

（確かめ）　M(7)=2^7-1=127 は素数、M(11)=2^11-1=2047は合成数、M(13)=2^13-1=8191は
　　　　　素数を見てみる。

S(1)=4 　　　　　　　　　　　　　      (mod 127)
S(2)=S(1)^2-2=4^2-2=14 　　　　　      (mod 127)
S(3)=S(2)^2-2=14^2-2=194≡67 　　      (mod 127)
S(4)=S(3)^2-2=67^2-2=4487≡42  　      (mod 127)
S(5)=S(4)^2-2=42^2-2=1762≡111       　(mod 127)
S(6)=S(5)^2-2=111^2-2=12319≡0         (mod 127)　・・・　従って、M(7)は素数

S(1)=4 　　　　　　　　　　　　　      (mod 2047)
S(2)=S(1)^2-2=4^2-2=14 　　　　　      (mod 2047)
S(3)=S(2)^2-2=14^2-2=194     　　      (mod 2047)
S(4)=S(3)^2-2=194^2-2=37634≡788       (mod 2047)
S(5)=S(4)^2-2=788^2-2=620942≡701      (mod 2047)
S(6)=S(5)^2-2=701^2-2=491399≡119      (mod 2047)
S(7)=S(6)^2-2=119^2-2=14159≡1877      (mod 2047)
S(8)=S(7)^2-2=1877^2-2=3523127≡240    (mod 2047)
S(9)=S(8)^2-2=240^2-2=57598≡282       (mod 2047)
S(10)=S(9)^2-2=282^2-2=79522≡1736     (mod 2047)

　もし、S(10)≡0 (mod 2047)であったなら、M(11)は素数であったのに、ここではそうではない
のだから、M(11)=2047(=23*89)は合成数

S(1)=4 　　　　　　　　　　　　　      (mod 8191)
S(2)=S(1)^2-2=4^2-2=14 　　　　　      (mod 8191)
S(3)=S(2)^2-2=14^2-2=194     　　      (mod 8191)
S(4)=S(3)^2-2=194^2-2=37634≡4870      (mod 8191)
S(5)=S(4)^2-2=4870^2-2=23716898≡3953  (mod 8191)
S(6)=S(5)^2-2=3953^2-2=15626207≡5970  (mod 8191)
S(7)=S(6)^2-2=5970^2-2=35640898≡1857  (mod 8191)
S(8)=S(7)^2-2=1857^2-2=3448447≡36     (mod 8191)
S(9)=S(8)^2-2=36^2-2=1294              (mod 8191)
S(10)=S(9)^2-2=1294^2-2=1674434≡3470  (mod 8191)
S(11)=S(10)^2-2=3470^2-2=12040898≡128 (mod 8191)
S(12)=S(11)-2=128^2-2=16382≡0         (mod 8191)　・・・　従って、M(13)は素数

　狐に抓まれる様に感じるが、確かに合っている。リュカの判定法が数が膨大なものに膨れ
上がって行くのに対し、レーマーの方法はmod計算内の数値で事済む。

　ふと、どのような経緯でこの法則を発見したものか？という疑問が湧く。
（ネットではこの判定法の証明とやらが書かれてあるが、これはあくまで論理的に後証明した
ものと思われる。）

　子供の頃から父親が熱心に取り組んでいる姿をみて、小さい子供ながら素数には人一倍
強い関心を持ち、自らもお手伝いの意味も含んで、素数を用いたたくさんの計算を経験して
いて、その中から素数に対する感覚が研ぎ澄まされていき、既にリュカによる漸化式的判定
方法をまねて作業する中で、ある日突然上記の法則に気づいてしまった、という私の勝手な
空想が広がっていくのでした。

　もうこの世にはいないヘンリー・レーマーにインタヴューするわけにはいかず、真相は闇の
中ですが、論理的に攻めたというより経験則から確信に至る経緯を通して、このテストはこ
の世に生まれ出たと思います。
（こんな法則が潜んでいたことをよくも発見したものだと感心します。）

　したがって、それまで誰も辿り着けなかった
M(257)=2^257-1=231584178474632390847141970017375815706539969331281128078915168015826259279871
なる想像を絶する数に対しても、
S(256)≠0 (mod 231584178474632390847141970017375815706539969331281128078915168015826259279871)
の確認よりM(257)は合成数である（即ちメルセンヌの予想は外れた。）と結論できた。

　実際、

231584178474632390847141970017375815706539969331281128078915168015826259279871
=535006138814359*1155685395246619182673033*374550598501810936581776630096313181393

　これが、１９３０年というからメルセンヌの予想(1644年）から286年後のことである。リュカの
発想とガウスのmod的世界観が混ざり合い、それが火花を発してレーマーテストが生まれ出
たと思える。


（追記）　「古の人の足跡を辿って」と題して、ＧＡＩ さんからの投稿です。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（平成２９年１０月２０日付け）

　メルセンヌ素数（M(p)=２^p-1（pは素数）)を見つけ出す方法に、リュカとレーマーのテスト方
法があり、リュカテストでは、

　素数pが 4*j+3 型であれば、S[0]=3、S[n]=S[n-1]²-2 (n≧1)　の漸化式とするとき、

初めて S[p-2]≡0 (mod M(p)) が成立すれば、M(p)=２^p-1 は素数である。

(実例)　p=7 は、4*j+3 型の素数で、メルセンヌ数が、M(7)=２⁷-1=128-1=127

　S[0]=3　、S[1]=S[0]^2-2=3^2-2=7　、S[2]=S[1]^2-2=7^2-2=47　、
　S[3]=S[2]^2-2=47^2-2=2207≡48 (mod 127)　、S[4]=S[3]^2-2=48^2-2=2302≡16 (mod 127)
　S[5]=S[4]^2-2=16^2-2=254≡0   (mod 127)

　よって、S{5]≡0 (mod M(7)) のテストを受け、M(7)=２⁷-1(=127)　が素数と判定。

　この道具を使うことにより、メルセンヌが素数になるであろうと予想していた

　　M(127)=２¹²⁷-1　(39桁の莫大な数）

も、この作業を地道に続けていけば可能となる。事実リュカは1876年（19年間も計算を続けて
の結果と読んだことがある。）M(127)が素数であることを確認したという。
（コンピュータではほんの数秒で確認可能）

　ところがメルセンヌが次に予想しているM(257)は、257が 4*j+1 型素数であるため、この方
法では確認できない。

　これに対し、レーマーがリュカの方法を改良し、リュカのテスト発表から約半世紀後、1930年
何とほんの僅かの差だが、

　どんな奇素数pでも、　S[0]=4、S[n]=S[n-1]²-2 (n≧1)　の漸化式とするとき、

初めて S[p-2]≡0 (mod M(p)) が成立すれば、M(p)=２^p-1 は素数である。

を公表し、リュカテストでは判定不可能だったタイプの素数に対してもチェック出来ることに
なった。こうしてメルセンヌが予想もしていなかったM(61)、M(89)などが素数であることが認
められていく。そして念願のM(257)は遂に1922年素数ではないことで決着がつくという。
なお、M(127)以降のものはM(521)まで進めないと存在しないという。（1952年決着)

　このようにリュカとレーマーのテストの違いはほんの初期条件S[0]の値だけである。リュカ
があれだけのテストを編み出す能力があればそこに気が付かなかったのか、また半世紀も
の間、誰も初期設定をS[0]=3からS[0]=4　へを行わなかったのか･･･不思議でなりません。
（コンピュータの確認計算では確かにこの変化は劇的に起こることは感じられますが、なぜ
それが可能なのかは分かりません。）

　ちなみにS[0]の値をいろいろ変化させてみると、S[0]=10 ならレーマーテストと同じ判定方
法がとれ、S[0]=14 ならS[p-3]≡0 (mod M(p)) で、M(p)：素数の判定がとれそうです。でも、
なぜこれらの初期値でそれが起こるのか霧の中です。


　らすかるさんからのコメントです。（平成２９年１０月２０日付け）

　 S[0]=4、S[n]=S[n-1]²-2 (n≧1) 　の漸化式とするとき、S[1]=14ですから、M(p)：素数の判
定がとれるのは当然ではないでしょうか。


　DD++さんからのコメントです。（平成２９年１０月２０日付け）

　なるほど、では初期値を変えることを閃いた GAI さんが、ぜひ S[0]=5 や S[0]=6 に変更し
たらどうなるかサクッと発表してください。もちろん、その方法できちんと素数である確認が
できるという証明付きで。


　ＧＡＩさんからのコメントです。（平成２９年１０月２０日付け）

　S[0]=5　のとき、pが 6j-1型の素数なら、S[p-1]=S[p]≡2 (mod M(p))

　　pが 6j+1型の素数なら、S[p]≡23 (mod M(p))

　S[0]=6　のとき、S[p-1]≡6 (mod M(p))

でしょうか。

　この証明ができれば夢のような話で、あくまで計算で出てくる結果で予想しているだけで･･･。
あッ！もしかしてS[0]=4でスタートすることで完璧なチェックがなされることを証明することが、
果たして簡単に証明可能なのか？をおっしゃりたい趣旨で言われていることなんですかね？
（でもリュカさんなら出来そうですが･･･；聞いてみないと分からないですかね。）


　DD++さんからのコメントです。（平成２９年１０月２０日付け）

　はい。元祖リュカテストについてはウェブ検索してもあまり出てこず、朧げな記憶を頼りにし
た話になってしまいますが、たしか証明はフィボナッチ数とリュカ数の関係からだったと思い
ます。つまり、

　F[0]=0、F[1]=1、F[n+2]=F[n+1]+F[n] で、0, 1, 1, 2, 3, 5, 8, …… というフィボナッチ数ができ
るのに対し、

　L[0]=2、L[1]=1、L[n+2]=L[n+1]+L[n] で、2, 1, 3, 4, 7, 11, 18, …… というリュカ数ができ、

これらの数の間には、　L[n]=F[n+1]+F[n-1] や F[2n]=F[n]L[n]　といった密接な関係があり
ます。
（→　参考：「リュカ≒フィボナッチ≒ピタゴラス」、「リュカ数」）

　そして、このリュカ数の ２ⁿ (n≧1) 番目だけ採用する、つまり S[n]=L[２ⁿ] とすると、

　　S[1]=3、S[n+1]=S[n]²-2

という数列ができていきます。この S[n] について、F[n] と L[n] の性質を使いながらいろいろ
調べていくと、元祖リュカテストが得られる、という話だったと思います。
（具体的にどうやるのだったかは忘れました）

　ということは、S[0]=3 というのは、適当に選んだ初項ではなく、2番目のリュカ数 L[2]=3 に
由来するものなので、S[0]=4 にした話を証明するにはフィボナッチ数やリュカ数を投げ捨て
て最初の一歩から考えないといけません。

　リュカはフィボナッチ数やリュカ数を一般化したリュカ数列（リュカ数を並べた数列という意
味ではない）を作ったわけですが、なぜそんな一般化をしようとしたのかと想像してみると…
やっぱり S[0] の一般化をしようとリュカが試行錯誤した形跡なのだろうと私は思うのですが、
いかがでしょう。


　ＧＡＩ さんからのコメントです。（平成２９年１０月２１日付け）

　なるほど、S[0]=3 と S[0]=4 とは全く異なる考え方による偶然の一つ違いであったのですか！
以前からフィボナッチ数列の漸化式とリュカ数列での漸化式は初期条件こそ異なるが、まっ
たく同形式の漸化式なのに、なぜわざわざ異なる呼び名を使用しているんだろうと不思議に
感じていました。

　さる本で、黄金分割比φ=(1+)/2に対して、

　φⁿ=((1+)/2)ⁿ=(L[n]+F[n]*)/2　(n=0,1,2,3,･･･）

　　{L[n]}：2,1,3,4,7,11,18,29,･･･　　{F[n]}：0,1,1,2,3,5,8,13,21,･･･

なるリュカ数列とフィボナッチ数列を使うと何かド・モアブルの定理を思わせることが可能なん
だと妙に感じ入ったことがありました。

　この数列の利用が、このメルセンヌ素数の決定に深く関わっていたとは知りませんでした。
あるサイトでこのレーマーテストの証明を見ましたけど、何やらガウスの平方剰余の相互法
則などを駆使しながら背理法を用い論理の綱渡りをサーカスよろしく、巧みにわたり切って
いる様を口をあんぐりと開けて眺めていました。いやいや先人の残された遺産は人類の宝
です。