フェルマー(Fermat)の小定理、と言うものをご存知でしょうか。それは
p を素数とするとき、p と互いに素な整数 a に対して
と言うものです。
さて、ある自然数が素数かどうか判定する方法として「エラストテネスの篩(ふるい)」と呼ばれる方法は有名ですが、これはアルゴリズムとしては合理的な方法ではありません。そこで実際には、フェルマーの小定理を利用して、ある自然数 n と、n と互いに素な整数 a を取ってきて
が成り立つとき、これは「素数ではない」と判定する方法(フェルマーテスト)が使われます。しかし「逆必ずしも真ならず」の言葉どおり、この方法では実際には素数でないものがチェック漏れする可能性を秘めています。そのようなチェック漏れする数、すなわち
n と互いに素なある整数 a に対して
が成り立つ数のことを a を底とする擬素数と言います。しかし、所詮は素数ではないのですから、a を取り替えてやれば、「素数ではない」と判定されるだろう、と、誰しもが期待します。しかし、その期待は、次の事実によって裏切られます。
n と互いに素な任意の整数 a に対して
が成り立つような自然数が(無数に)存在することが知られているのです ! そのような数のことをカーマイケル数(Carmichael number)と言います。ちなみに最小のカーマイケル数は 561 = 3 × 11 × 17 であることが知られています。
参考サイト : フェルマーテストによる素数判定
