p を素数とし、a を p と互いに素な整数とするとき、

a^p-1 ≡ 1   (mod p)

が成り立つ。

入試でもおなじみのフェルマーの小定理ですが、これの対偶を考えます。

つまり、自然数 n が、n と互いに素な自然数 a に対して

a^n-1 ≡ 1   (mod n)  ・・・①

を満たさないなら、n は素数でない、ということです。

これを使って、自然数 n が素数かどうかを確率的に判定する方法を「フェルマーテスト」といいます。

自然数 n に対して、ある a で①が成り立たなければ n は素数ではなく、①が成り立てば素数かもしれません。

「素数かもしれない」というのは、例えば a = 2 のとき、n = 341 とすると①を満たしますが、341は合成数です。

このように、合成数であるにも関わらず、ある意味で素数のように見えてしまうものを「擬素数」と呼びます（今回の判定法による擬素数はフェルマー擬素数といいます）。

でも、色々な a で成り立てばさすがにそれもう素数なのでは……？

と思いたくなりますが、残念ながらそれは言えません。

タイトルの561は当然合成数です。

3で割り切れることがすぐにわかります。

ところが、n = 561と互いに素な任意の自然数 a に対して、①が成り立ってしまいます。

このような自然数を「カーマイケル数」と呼び、無数に存在します。

561は最小のカーマイケル数です。

結局役に立たなさそうな判定法ですが、素数で順にちまちま割っていく素数判定法よりも計算が早く、大きい素数を探すのに役立ちます。

また、フェルマーテストを改良した判定法なども存在します。