フェルマーの小定理
フェルマーテストは、フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。
フェルマーの小定理の対偶をとると、これは次のように、自然数 n が合成数であるための十分条件を与える。
3通りの証明を示す。