Teste de primalidade de Fermat

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.

Teorema

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

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

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

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

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

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

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

Prova do teorema

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

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

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

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

vemos que $i \equiv j\pmod m$

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

com isso $i = j$

porque $0 \le |i - j| < m$,

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

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

Conclui-se que:

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

Já que

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

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

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

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.

Ver também

• Pseudoprimalidade
• Último Teorema de Fermat