【１】フェルマーの定理

　ｐが素数なら，ａ^p−ａはｐで割り切れる．

　ｐが素数なら，ａとｐは互いの素ならば，ａ^p-1−１はｐで割り切れる．

　ｎが素数であることは２^n−１が素数であるための必要条件です．しかし，逆の十分性は成り立ちません．

　　２^2−１＝３　　（素数）

　　２^3−１＝７　　（素数）

　　２^5−１＝３１　　（素数）

　　２^7−１＝１２７　　（素数）

　　２^11−１＝２０４７＝２３・８９　　（非素数）

　　２^13−１＝８１９１　　（素数）

　フェルマーの定理の応用性は高く，

　　２^4−１＝１５　　（非素数）

　　２^6−１＝６３　　（非素数）

　　２^8−１＝２５５　　（非素数）

　　２^9−１＝５１１＝７・７３　　（非素数）

　　２^12−１＝１０２３＝３・３４１　　（非素数）

などはすぐ判定できます．

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

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

　素数ｐに対して

　　Ｍp＝２^p−１

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

　　Ｍ13＝８１９１　　　　（素数）

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

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

は素数であるが，

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

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

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

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

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

　　２^q＝１　　（ｍｏｄｐ）

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

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

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

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

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

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

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

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

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