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.
(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.
Seja
,
consideramos os conjuntos
e
e percebemos que
.
Seja
e
vemos que
porque
,
com isso
porque
,
então os números 
são incongruentes entre si
.
Então
são congruentes, em alguma ordem, com os números
.
Conclui-se que:

Se tivermos
, ou seja,
é primo, podemos cancelar o fator
, e obtemos:
,
aos inteiros
o que conclui a prova.
Infelizmente existem números que passam o teste de Fermat para todas as bases para as quais são relativamente primos – são os chamados números de Carmichael, e são infinitos. Como tal, pode-se fazer o Teste de pseudoprimalidade forte:
- Dado

- Escreve-se
, em que
é ímpar
- Escolher aleatoriamente

- Calcular

- Se
, então
passa
- Calcular
para 
- Se
para algum
, então
passa
- Caso contrário
falha.
O teste deve ser repetido para
bases diferentes. A probabilidade de um número composto
passar
testes é de 1 em 4r. Se
passar o teste para 100 bases diferentes, então a probabilidade de
ser composto é menor que 10−60.
Sabe-se que, com exceção dos números
e
, todos os outros números primos são expresso pela fórmula
. Mas sabe-se que a imensa maioria dos números expresso pela fórmula
não são números primos. O estudo dos não-primos da forma
leva à igualdade
Então: dado um número inteiro positivo qualquer
, se não ocorrer nenhum par de números inteiros positivos
que satisfaça a igualdade acima, afirma-se que os números
são números primos gêmeos.
Se não ocorrer nenhum par
com sinais iguais e ocorrer ao menos um par
com sinais diferentes que satisfaça a equação, afirma-se que
é primo e
não é primo.
Se não ocorrer nenhum par
com sinais diferentes e ocorrer ao menos um par
com sinais iguais que satisfaça a equação, afirma-se que
é primo e
não é primo.