【１】フェルマーの定理

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

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

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

　　２^2−１＝３　　（素数）

　　２^3−１＝７　　（素数）

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

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

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

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

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

【２】フェルマーの発見

　フェルマーは

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

を発見しています．

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

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

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

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

　　１３７４３８９５３４７１＝２２３・６１６３１８７７

　フェルマーは，この発見は

［１］ｎが素数でないとき，２^n−１は素数ではない

［２］ｎが素数のとき，２^n−２は２ｎで割り切れる

［３］ｎが素数であり，ｐが２^n−１の素因数であるとき，ｐ−１の倍数である

に基づいていると書いています．

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

【３】フェルマー・テスト

　ｐが素数，ａとｐは互いに素ならば，ａ^p-1−１はｐで割り切れる・・・は，任意の０＜ａ＜ｐに対して，ａ^p-1＝１　　（ｍｏｄｐ）が成り立つと同義です．

　そこで，ｎの素数性を知りたいとき，ｎより小さい任意のａに対して

　　ａ^n-1＝１　　（ｍｏｄｎ）

が成り立たなければ，ｎは素数でないことになります．

　成り立てば素数である可能性は高く，しかし，多くのａについてこれが成り立てば，素数である可能性は非常に高くなるというわけです．

　しかし，擬素数と判定されるいくつかの数があり，さらに，ｎと互いに素なすべてのｎに対してこれが成り立つ合成数がカーマイケル数（完全擬素数）です．

５６１＝３・１１・１７　　（最小のカーマイケル数）

１７２９＝１９・９１

２８２１７・１３・３１

１７２０８１＝７・１３・３１・６１

　カーマイケル数を配慮する必要をなくすように改良したものがミラー・ラビンテストです．

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