フェルマーの小定理
フェルマーテストが「合成数」と出力したとき、上のフェルマーの小定理の対偶によって n {\displaystyle n} は実際に合成数である。しかし、上の対偶は十分条件を与えるのみで必要条件を与えるものではないので、「確率的素数」と出力された場合でも n {\displaystyle n} は実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。
疑わしければ、「確率的素数」と出力された場合にはまた異なる a {\displaystyle a} を用いて再びテストを行う。十分な回数だけ a {\displaystyle a} を取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。
しかし、カーマイケル数または絶対擬素数と呼ばれる "反例" もある。カーマイケル数は合成数であるにもかかわらず、ほとんどいかなる a {\displaystyle a} を用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。
フェルマーテストを改善するアルゴリズムとしては、ミラー–ラビン素数判定法やAKS素数判定法がある。
p {\displaystyle p} を素数とし、 a {\displaystyle a} を整数とすると、
a p ≡ a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}}
が成立すると言う定理である。また、 p {\displaystyle p} を素数とし、 a {\displaystyle a} を p {\displaystyle p} の倍数でない整数( a {\displaystyle a} と p {\displaystyle p} は互いに素)とするときに、
a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
が成立する。すなわち、 a {\displaystyle a} の p − 1 {\displaystyle p-1} 乗を p {\displaystyle p} で割った余りは 1 {\displaystyle 1} である。有名なフェルマーの最終定理と区別するためにあえて「小」定理と称されている。
この定理はピエール・ド・フェルマーの名を冠するが、フェルマーの他の予想と同じく、フェルマー自身によって証明が与えられていたことが確認されているわけではない。この定理に対する証明はゴットフリート・ライプニッツによって初めて与えられた。