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í: 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.
Supongamos que se quiere determinar si n = 221 es primo.
Escogiendo aleatoriamente 1 < a < 221, digamos a = 38, se puede chequear la expresión para determinar si se cumple: luego 221 puede ser primo, o también puede que 38 sea un número que falsee el test, de manera que tomamos otro a, esta vez 24: Luego 221 es compuesto y 38 era en efecto un número que falsaba el test.
El programa de cifrado PGP aprovecha esta propiedad del teorema para comprobar si los grandes números aleatorios que elige son primos.