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.
Os números compostos da forma
são obtidos pela multiplicação de dois números da forma
onde estes dois números podem ser ambos primos ou ambos compostos e também pode ser o produto de um número primo por um número composto como vemos abaixo
que podemos escrever
Vemos então que esta igualdade só existe se
Se esta igualdade não existir para sinais iguais ou diferentes, então o par de números
não existe como números compostos, logo o par de números
serão números primos gêmeos.
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.