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.

Teorema

(Assuma-se ${\displaystyle \operatorname {mdc} (a,b)}$ como o Máximo divisor comum entre ${\displaystyle a}$ e ${\displaystyle b}$).

Se ${\displaystyle m}$ é primo, então para qualquer ${\displaystyle a}$ tal que ${\displaystyle \operatorname {mdc} (a,m)=1}$, temos:

${\displaystyle a^{m-1}\equiv 1{\pmod {m}}}$

Se ${\displaystyle m}$ não é primo, ainda é possível (embora pouco provável) que o supradito se verifique.

Se ${\displaystyle m}$ é ímpar composto, e ${\displaystyle a}$ um inteiro tal que ${\displaystyle \operatorname {mdc} (a,m)=1}$ e

${\displaystyle a^{m-1}\equiv 1{\pmod {m}}}$

diz-se que ${\displaystyle m}$ é pseudoprimo para a base ${\displaystyle a}$, i.e., é um número não primo que passa o teste de Fermat.

Prova do teorema

Seja ${\displaystyle \operatorname {mdc} (a,m)=1}$,

consideramos os conjuntos ${\displaystyle \{1,2,3,\ldots ,m-1\}}$ e ${\displaystyle \{a,2a,3a,\ldots ,(m-1)a\}}$

e percebemos que ${\displaystyle \{a,2a,3a,\ldots ,(m-1)a\}\not \equiv 0{\pmod {m}}}$.

Seja ${\displaystyle i,j\in \{1,2,3,\ldots ,m-1\}}$ e ${\displaystyle ia\equiv ja{\pmod {m}}}$

vemos que ${\displaystyle i\equiv j{\pmod {m}}}$

porque ${\displaystyle \operatorname {mdc} (a,m)=1}$,

com isso ${\displaystyle i=j}$

porque ${\displaystyle 0\leq |i-j|<m}$,

então os números ${\displaystyle \{a,2a,3a,\ldots ,(m-1)a\}\not \equiv 0{\pmod {m}}}$
são incongruentes entre si ${\displaystyle {\pmod {m}}}$.

Então ${\displaystyle \{a,2a,3a,\ldots ,(m-1)a\}}$ são congruentes, em alguma ordem, com os números ${\displaystyle 1,2,3,\ldots ,m-1}$.

Conclui-se que:

${\displaystyle (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}}}$

Se tivermos

${\displaystyle \operatorname {mdc} (m,(m-1)!)=1}$ , ou seja, ${\displaystyle m}$ é primo, podemos cancelar o fator ${\displaystyle (m-1)!}$, e obtemos:

${\displaystyle a^{m-1}\equiv 1{\pmod {m}}}$, ${\displaystyle \forall m\in }$ 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 ${\displaystyle m}$
• Escreve-se ${\displaystyle m-1=2^{8}t\,\!}$, em que ${\displaystyle t}$ é ímpar
• Escolher aleatoriamente ${\displaystyle a\in [1,m[}$
• Calcular ${\displaystyle h\equiv a^{t}{\pmod {m}}\,\!}$
• Se ${\displaystyle h=\pm 1}$, então ${\displaystyle m}$ passa
• Calcular ${\displaystyle h^{i}=a^{(2^{i})t}}$ para ${\displaystyle i=1,2,...,8}$
• Se ${\displaystyle h^{i}=-1\,\!}$ para algum ${\displaystyle i<8}$, então ${\displaystyle m}$ passa
• Caso contrário ${\displaystyle m}$ falha.

O teste deve ser repetido para ${\displaystyle r}$ bases diferentes. A probabilidade de um número composto ${\displaystyle m}$ passar ${\displaystyle r}$ testes é de 1 em 4^r. Se ${\displaystyle m}$ passar o teste para 100 bases diferentes, então a probabilidade de ${\displaystyle m}$ ser composto é menor que 10⁻⁶⁰.

Um teste elementar e preciso de primalidade

Sabe-se que, com exceção dos números ${\displaystyle 2}$ e ${\displaystyle 3}$, todos os outros números primos são expresso pela fórmula ${\displaystyle I_{p}=6K\pm 1}$ . Mas sabe-se que a imensa maioria dos números expresso pela fórmula ${\displaystyle I_{p}=6K\pm 1}$ não são números primos.

Os números compostos da forma ${\displaystyle I=6K\pm 1}$ são obtidos pela multiplicação de dois números da forma ${\displaystyle I=6K\pm 1}$ 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

${\displaystyle 6K\pm 1=(6K_{2}\pm 1)(6K_{3}\pm 1)=6.6K_{2}.K_{3}\pm 6K_{2}.1\pm 6K_{3}.1\pm 1}$ que podemos escrever

${\displaystyle 6K\pm 1=6(6K_{2}K_{3}\pm K_{2}\pm K_{3})\pm 1}$

Vemos então que esta igualdade só existe se

${\displaystyle K=6K_{2}K_{3}\pm K_{2}\pm K_{3}}$

Se esta igualdade não existir para sinais iguais ou diferentes, então o par de números ${\displaystyle 6K\pm 1}$ não existe como números compostos, logo o par de números ${\displaystyle 6K\pm 1}$ serão números primos gêmeos.

Então: dado um número inteiro positivo qualquer ${\displaystyle K}$, se não ocorrer nenhum par de números inteiros positivos ${\displaystyle K_{2},K_{3}}$ que satisfaça a igualdade acima, afirma-se que os números ${\displaystyle I_{p}=6K\pm 1}$ são números primos gêmeos.

Se não ocorrer nenhum par ${\displaystyle K_{2},K_{3}}$ com sinais iguais e ocorrer ao menos um par ${\displaystyle K_{2},K_{3}}$ com sinais diferentes que satisfaça a equação, afirma-se que ${\displaystyle I_{p}=6K+1}$ é primo e ${\displaystyle I=6K-1}$ não é primo.

Se não ocorrer nenhum par ${\displaystyle K_{2},K_{3}}$ com sinais diferentes e ocorrer ao menos um par ${\displaystyle K_{2},K_{3}}$ com sinais iguais que satisfaça a equação, afirma-se que ${\displaystyle I_{p}=6K-1}$ é primo e ${\displaystyle I=6K+1}$ não é primo.

Ver também

• Pseudoprimalidade
• Último Teorema de Fermat

• Portal da matemática
• Portal das tecnologias de informação