まずはおさらいから

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

【１】フェルマーの小定理

　素数ｐの倍数でない任意の数ａを選ぶと，

　　ａ^p-1＝１　　（ｍｏｄｐ）

が成り立つ．もし，この余りが１でなければ，最初に選んだｐは素数ではないことになるというのがフェルマーの指数判定法である．この方法は素数であるための必要条件を効率的にチェックできるが，絶対的なものではなく，いくつかの合成数がパスしてしまう．

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

【２】カーマイケル数の特徴づけ

　どんな底に対しても

　　ａ^p−ａ

がｐで割り切れるとき，それがカーマイケル数である．

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

［Ｑ］ｐ1，ｐ2，ｐ3は素数で，

　　ｐ1＝６ｎ＋１，ｐ2＝１２ｎ＋１，ｐ3＝１８ｎ＋１

このとき，ｐ1ｐ2ｐ3はカーマイケル数であることを示せ．

［１］ｐ1ｐ2ｐ3≠０　　（ｍｏｄｐ1^2）

［２］ｐ1ｐ2ｐ3≠０　　（ｍｏｄｐ2^2）

［３］ｐ1ｐ2ｐ3≠０　　（ｍｏｄｐ3^2）

［４］ｐ1ｐ2ｐ3＝１　　（ｍｏｄ６ｎ）

［５］ｐ1ｐ2ｐ3＝１　　（ｍｏｄ１２ｎ）

［６］ｐ1ｐ2ｐ3＝１　　（ｍｏｄ１８ｎ）

であることがいえればよいことになる．

　ｐ1ｐ2ｐ3＝６・１２・１８ｎ^3＋（６・１２＋１２・１８＋１８・６）ｎ^2＋（６＋１２＋１８）ｎ＋１より，［４］［５］［６］→ＯＫ

　ｐ1ｐ2＝６・１２ｎ^2＋（６＋１２）ｎ＋１より［３］→ＯＫ

　ｐ2ｐ3＝１２・１８ｎ^2＋（１２＋１８）ｎ＋１より［１］→ＯＫ

　ｐ3ｐ1＝１８・６ｎ^2＋（１８＋６）ｎ＋１より［２］→ＯＫ

これらの条件は，ｎ＝１，６，３５のとき満たされる．

　ｎ＝１：７・１３・１９はカーマイケル数である．

　ｎ＝６：３７・７３・１０９はカーマイケル数である．

　ｎ＝３５：２１１・４２１・６３１はカーマイケル数である．

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