Pequeno teorema 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

Retrato de Pierre de Fermat

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

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

$a^{m-1}\equiv 1(\mathrm{mod}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 $\mathrm{mdc}(a,m)=1$ e

$a^{m-1}\equiv 1(\mathrm{mod}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 $\mathrm{mdc}(a,m)=1$,

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

e percebemos que $\{a,2a,3a,\dots ,(m-1)a\}\equiv ̸0(\mathrm{mod}m)$.

Seja $i,j\in \{1,2,3,\dots ,m-1\}$ e $ia\equiv ja(\mathrm{mod}m)$

vemos que $i\equiv j(\mathrm{mod}m)$

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

com isso $i=j$

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

então os números $\{a,2a,3a,\dots ,(m-1)a\}\equiv ̸0(\mathrm{mod}m)$
são incongruentes entre si $(\mathrm{mod}m)$.

Então $\{a,2a,3a,\dots ,(m-1)a\}$ são congruentes, em alguma ordem, com os números $1,2,3,\dots ,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⟹(m-1)!\equiv a^{m-1}\cdot (m-1)!(\mathrm{mod}m)$

Se tivermos

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

$a^{m-1}\equiv 1(\mathrm{mod}m)$, $\mathrm{\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 $m$
• Escreve-se $m-1=2^{8}t$, em que $t$ é ímpar
• Escolher aleatoriamente $a\in [1,m[$
• Calcular $h\equiv a^t(\mathrm{mod}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 $I_p=6K\pm 1$ . Mas sabe-se que a imensa maioria dos números expresso pela fórmula $I_p=6K\pm 1$ não são números primos.

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

$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

$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

$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 $6K\pm 1$ não existe como números compostos, logo o par de números $6K\pm 1$ serão números primos gêmeos.

Então: dado um número inteiro positivo qualquer $K$, se não ocorrer nenhum par de números inteiros positivos $K_2,K_3$ que satisfaça a igualdade acima, afirma-se que os números $I_p=6K\pm 1$ são números primos gêmeos.

Se não ocorrer nenhum par $K_2,K_3$ com sinais iguais e ocorrer ao menos um par $K_2,K_3$ com sinais diferentes que satisfaça a equação, afirma-se que $I_p=6K+1$ é primo e $I=6K-1$ não é primo.

Se não ocorrer nenhum par $K_2,K_3$ com sinais diferentes e ocorrer ao menos um par $K_2,K_3$ com sinais iguais que satisfaça a equação, afirma-se que $I_p=6K-1$ é primo e $I=6K+1$ não é primo.

Ver também

• Pseudoprimalidade
• Último Teorema de Fermat