（その９）（その１０）ではシェルピンスキー数，すなわち，ｑ＝２^kｐ＋１（ｋ≧０）という形の数において，あるきまったｐを選んで，ｋを変えていき，すべて合成数となるようなｐを探し出した．

　それに対して，ａを底とするフェルマー・テスト，すなわち，ｇｃｄ（ａ，ｎ）＝１となるある自然数ａに対して，

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

がすべてのａに対して成り立つとき，ｎをカーマイケル数という．

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

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

　ｐが素数であるならば，ｇｃｄ（ａ，ｎ）＝１となる任意の自然数ａに対して，

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

が成り立つ．

　この定理の対偶は，ｇｃｄ（ａ，ｎ）＝１となるある自然数ａに対して，

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

となるならば，ｎは合成数である．

　たとえば，ｎ＝１１７，ａ＝２の場合，

　　２^7＝１２８＝１１　　（ｍｏｄ１１７）

　　１１^2＝１２１＝４＝２^2　　（ｍｏｄ１１７）

　　１１６＝７・１６＋４

より

　　２^116＝（２^7）^16（２^4）＝１１^16・２^4＝２^16・２^4＝２^20

＝２^14・２^6＝１１^2・２^6＝２^2・２^6＝２^8＝２^7・２＝１１・２＝２２　　（ｍｏｄ１１７）

　　２^116≠１　　（ｍｏｄ１１７）→１１７は合成数である．（実際，１１７＝３^2・１３）

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

　しかし，フェルマーの小定理の逆は真ではない．たとえば，ｎ＝３４１，ａ＝２の場合，３４１＝１１・３１にもかかわらず

　　２^340＝１　　（ｍｏｄ３４１）

となる．

（証）

　　１０２３＝３４１・３

　　２^10＝１０２４＝１　　（ｍｏｄ３４１）

より

　　２^340＝（２^10）^34＝１　　（ｍｏｄ３４１）

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

　それでも，ｎ＝３４１，ａ＝３の場合，

　　３^340≠１　　（ｍｏｄ３４１）

となる．

（証）

　　３^10＝５９０４９＝５６　　（ｍｏｄ３４１）

　　５６^3＝１７５６１６＝１　　（ｍｏｄ３４１）

より

３^340＝（３^10）^34＝５６^34＝（５６^3）^11・５６＝５６≠１　　（ｍｏｄ３４１）

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