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

　素数ｐに対して

　　Ｍp＝２^p−１

をメルセンヌ数をいいます．

　　Ｍ13＝８１９１　　　　（素数）

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

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

は素数であるが，

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

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

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

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

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

　　２^q＝１　　（ｍｏｄｐ）

ならば，ｐ＝１　　（ｍｏｄｑ）であるを用いることにする．

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

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

　ｐ≦９０までの素数がＭ13の素因数でないことを示す．命題よりｐ＝１　）ｍｏｄ１３）は奇数であることを考慮すると，ｐ＝２６ｎ＋１型と書けるので，　　ｐ＝２７，５３，７９

が候補となる．２７は素数でなく，５３，７９は８１９１の約数でない．

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

　ｐ≦３６２までの素数がＭ17の素因数でないことを示す．命題よりｐ＝１　）ｍｏｄ１７）は奇数であることを考慮すると，ｐ＝３４ｎ＋１型と書けるので，　　ｐ＝３５，６９，１０３，１３７，１７１，２０５，２３９，２７３，３０７，３４１

が候補となる．３５，６９，１７１，２０５，２７３，３４１は素数でなく，１０３，１３７，２３９，３０７は１３１０７１の約数でない．

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