合成数」と出力して終了。合成数」と出力して終了する。確率的素数」と出力して終了する。実際に素数であるとは限らない。素数ではないにもかかわらず「確率的素数」と判定されてしまう合成数は擬素数と呼ばれる。用いて再びテストを行う。取り替えて繰り返せば、フェルマーテストが「確率的素数」と判定した数は実際に素数である可能性が高い。用いても「確率的素数」と判定されてしまう。従って、フェルマーテストは完全な素数判定法ではない。フェルマーテストを改善するアルゴリズムとしては、ラビン-ミラー素数判定法やAKS素数判定法がある。一般化[編集]フェルマーの小定理・オイラーの定理は一般の有限群の定理に拡張できる。