Um exemplo particularmente simples de um teste probabilístico é o teste de primalidade de Fermat, que se baseia no fato (pequeno teorema de Fermat) de que np≡n (mod p) para qualquer n se p for um número primo. Se temos um número b que queremos testar quanto à primalidade, calculamos nb (mod b) para um valor aleatório de n como nosso teste. Uma falha neste teste é que existem alguns números compostos (os números de Carmichael) que satisfazem a identidade de Fermat, mesmo que não sejam primos, portanto o teste não tem como distinguir entre números primos e números de Carmichael. Os números de Carmichael são substancialmente mais raros que os números primos, portanto, esse teste pode ser útil para fins práticos. Extensões mais poderosas do teste de primalidade de Fermat, como os testes de Baillie-PSW, Miller-Rabin e Solovay-Strassen, certamente falharão pelo menos parte do tempo quando aplicadas a um número composto.
Qual é um caso direto de um teste probabilístico?
o teste de primalidade de Fermat,