どんな底に対しても

　　ａ^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＋（１８＋６）ｎ＋１より［２］→ＯＫ

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

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

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

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

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

ところで，

　　５６１＝３・１１・１７

　　１１０５＝５・１３・１７

　　１７２９＝７・１３・１９

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

　　２８２１＝７・１３・３１

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

　　８９１１＝７・１９・６７

　　１０５８５＝５・２９・７３です

から，カーマイケル数は少なくとも３つの素因数をもつ．

［Ｑ］カーマイケル数は少なくとも３つの素因数をもつことを証明せよ

（証明）

　ｐ1，ｐ2は奇素数で，ｐ1＜ｐ2とする．ｎ＝ｐ1ｐ2がカーマイケル数であると仮定すると

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

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

［３］ｐ1ｐ2＝１　　（ｍｏｄｐ1−１）

［４］ｐ1ｐ2＝１　　（ｍｏｄｐ2−１）

が成り立たなければならない．

　　１＜ｐ1−１＜ｐ2−１

　　ｐ1ｐ2−１＝ｐ1（ｐ2−１）＋ｐ1−１

より，

　　ｐ1ｐ2−１＝ｐ1−１　　（ｍｏｄｐ2−１）

　これは

　　［４］ｐ1ｐ2−１＝０　　（ｍｏｄｐ2−１）

に矛盾．したがって，カーマイケル数は素因数を２つだけもつことはない．→カーマイケル数は少なくとも３つの素因数をもつ．

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