Teste de primalidade de Fermat

O Teorema de Fermat, que originou o Teste de primalidade de Fermat, oferece um teste simples e eficiente para ignorar números não-primos. Qualquer número que falhe o teste não é primo.

Teorema

(Assuma-se como o Máximo divisor comum entre e ).

Se é primo, então para qualquer tal que , temos:

Se não é primo, ainda é possível (embora pouco provável) que o supradito se verifique.

Se é ímpar composto, e um inteiro tal que e

diz-se que é pseudoprimo para a base , i.e., é um número não primo que passa o teste de Fermat.