Saltar para o conteúdo

Pequeno teorema de Fermat

Origem: Wikipédia, a enciclopédia livre.
Pierre 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.

Retrato de Pierre de Fermat

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

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.