【２】メルセンヌ数の素数性判定

　　Ｍ13＝８１９１　　　　（素数）

　　Ｍ17＝１３１０７１　　（素数）

　　Ｍ19＝５２４２８７　　（素数）

Ｍ23＝８３８８６０７　　　　　　　（非素数）

　　Ｍ29＝５３６８７０９１１　　　　　（非素数）

　　Ｍ37＝１３７４３８９５３４７１　　（非素数）

　に対して，

　　√８１９１＝９０．５・・・

　　√１３１０７１＝３６２．０・・・

　　√５２４２８７＝７２４．０・・・

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

までのすべての素数が素因数であるかどうかを確認するのは電卓を用いても一苦労です．そこで，

命題：ｐを奇素数，ｑを素数とするとき，

　　２^q＝１　　（ｍｏｄｐ）ならば，ｐ＝１　　（ｍｏｄｑ）

である

ことを用いることにします．すなわち，メルセンヌ数２^n−１が合成数であるならば，因数はあるｋに対してｋｎ＋１型でというものす．

［１］Ｍ13＝８１９１　　　　（素数）

ｐ≦９０までの素数がＭ13の素因数でないことを示す．命題よりｐ＝１３ｎ＋１．ｎ＝１は偶数なので，素因数となりうるのはｐ＝２６ｎ＋１型と書ける．ｐ＝２７，５３，７９が候補となるが，２７は素数でなく，５３，７９は８１９１の約数でない．

［２］Ｍ17＝１３１０７１　　（素数）

ｐ≦３６２までの素数がＭ17の素因数でないことを示す．ｐ＝３４ｎ＋１型と書けるので，ｐ＝３５，６９，１０３，１３７，１７１，２０５，２３９，２７３，３０７，３４１が候補となる．３５，６９，１７１，２０５，２７３，３４１は素数でなく，１０３，１３７，２３９，３０７は１３１０７１の約数でない．

［３］Ｍ11＝２^11−１　　（非素数）

ｐ＝１１ｎ＋１，ｎ＝１は偶数なので，素因数となりうるのは ｐ＝２２ｎ＋１型と書ける．２３は早速素数なので調べてみると

２３＝２・１１＋１

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

［４］Ｍ２３＝２^23−１　　（非素数）

ｐ＝２３ｎ＋１，ｎ＝１は偶数なので，素因数となりうるのは ｐ＝４６ｎ＋１型と書ける．４７は早速素数なので調べてみると

　　４７＝２・２３＋１

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

［５］Ｍ37＝２^37−１　　（非素数）

ｐ＝３７ｎ＋１，ｎ＝１は偶数なので，ｐ＝７４ｎ＋１型と書ける．

　　ｎ＝１：ｐ＝７５（非素数）

　　ｎ＝２：ｐ＝１４９（素数）であるが，因数ではない．

　　ｎ＝３：ｐ＝２２３（素数）であり，因数でもある．

　　２２３＝６・３７＋１

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

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