Abrir menu principal

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

Ver tambémEditar