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.

TeoremaEditar

(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.

Prova do teoremaEditar

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.

ContrapartidasEditar

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 primalidadeEditar

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.

Ver tambémEditar