Pequeno teorema de Fermat: diferenças entre revisões
m Removing Link GA template (handled by wikidata) |
Inseri uma condição que estava omitida |
||
Linha 37: | Linha 37: | ||
Conclui-se que: |
Conclui-se que: |
||
:<math>(m - 1)! = 1\cdot 2\cdot 3\cdot 4 \cdots (m - 1) \equiv a\cdot 2a\cdot 3a\cdot 4a \cdots (m - 1)a \implies (m - 1)! \equiv a^{m - 1}\cdot(m - 1)!\pmod m</math> |
:<math>(m - 1)! = 1\cdot 2\cdot 3\cdot 4 \cdots (m - 1) \equiv a\cdot 2a\cdot 3a\cdot 4a \cdots (m - 1)a \implies (m - 1)! \equiv a^{m - 1}\cdot(m - 1)!\pmod m</math> |
||
Se tivermos |
|||
Já que |
|||
:<math>\operatorname{mdc}(m,(m - 1)!) = 1</math> |
:<math>\operatorname{mdc}(m,(m - 1)!) = 1</math> , ou seja, <math>m</math> é primo, podemos cancelar o fator <math>(m - 1)! </math>, e obtemos: |
||
:<math>a^{m-1}\equiv 1\pmod m</math><br />o que conclui a prova. |
:<math>a^{m-1}\equiv 1\pmod m</math>, <math>\forall m \in </math> aos inteiros<br />o que conclui a prova. |
||
== Contrapartidas == |
== Contrapartidas == |
Revisão das 20h54min de 4 de outubro de 2016
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
(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
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
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 2 e 3, todos os outros números primos são expresso pela fórmula Ip=6K±1. Mas sabe-se que a imensa maioria dos números expresso pela fórmula Ip=6K±1 não são números primos. O estudo dos não-primos da forma Ip=6K±1 leva à igualdade
K=6k2k3±k2±k3.
Então: dado um número inteiro positivo qualquer K, se não ocorrer nenhum par de números inteiros positivos k2,k3 que satisfaça a igualdade acima, afirma-se que os números Ip=6K±1 são números primos gêmeos.
Se não ocorrer nenhum par k2,k3 com sinais iguais e ocorrer ao menos um par k2,k3 com sinais diferentes que satisfaça a equação, afirma-se que Ip=6K+1 é primo e Ip=6K-1 não é primo.
Se não ocorrer nenhum par k2,k3 com sinais diferentes e ocorrer ao menos um par k2,k3 com sinais iguais que satisfaça a equação, afirma-se que Ip=6K-1 é primo e Ip=6K+1 não é primo.