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.
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.
Contrapartidas
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.
Um teste elementar e preciso de primalidade
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.