Teste de primalidade de Fermat

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Pequeno teorema de Fermat)
Saltar para a navegação Saltar para a pesquisa

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.

Teorema[editar | editar código-fonte]

(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 teorema[editar | editar código-fonte]

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.

Contrapartidas[editar | editar código-fonte]

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[editar | editar código-fonte]

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ém[editar | editar código-fonte]