El test de primalidad de Fermat es un algoritmo probabilístico que hace uso del pequeño teorema de Fermat. Este teorema enuncia que si p es primo y a es coprimo con p, entonces ap-1 - 1 es divisible por p. Esto también se puede expresar así: 

ap-1 ≡ 1 (mod p).Resulta que el recíproco de este teorema suele ser verdad: si p es compuesto, entonces ap-1 es poco probable que sea congruente con 1 módulo p para un valor arbitrario de a. Sin embargo, tomando números compuestos n y eligiendo un a coprimo con estos, algunos de ellos pueden hacer fallar este test. Estos números se denominan pseudoprimos.