古代ギリシャ人はｎ＝２，３，５，７，（１３）のとき，２^n−１が素数になることを知っていました．ｎ＝１１の場合，素数でないこと

　　２^11−１＝２０４７＝２３・８９

を発見したのは，ドイツの数学者レギウス（ウーリヒ・リーガー）でした（１５３６年）．

　その後，メルセンヌ素数にｎ＝１７，１９，３１が追加されましたが，フェルマーは

　　２^23−１＝８３８８６０７＝４７・１７８４８１

　　２^37−１＝１３７４３８９５３４７１＝２２３・６１６３１８７７

を発見しています．

　これらの素因数についてみると，

　　２３＝２・１１＋１

　　４７＝２・２３＋１

２２３＝６・３７＋１

という関係がみえてくる．すなわち，２^n−１が合成数であるならば，それはあるｋに対してｋｎ＋１であるのだろうか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ここではＭ23＝８３８８６０７の非素数性を判定してみよう．

　√８３８８６０７＝２８９６．３・・・

までの範囲の素数を確認するのは電卓を用いても一苦労である．しかし，この数が素数卯でないことなら証明できるかもしれない．

　そこで，命題：ｐを奇素数，ｑを素数とする

　　２^q＝１　　（ｍｏｄｐ）

ならば，ｐ＝１　　（ｍｏｄｑ）であるを用いると，素因数となりうるのは ｐ＝４６ｎ＋１型と書ける．４７は早速素数なので調べてみると

　　８３８８６０７＝４７・１７８４８１　　（ＱＥＤ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝