Para um primo \(p\), o Pequeno Teorema de Fermat afirma que \[\begin{align*}
a^p&\equiv a\pmod p\quad\mbox{para todo}\quad a\in \Z;\\
a^{p-1}&\equiv 1\pmod p\quad\mbox{para todo}\quad a\in \Z\mbox{ tal que }p\nmid a.
\end{align*}\]
O Pequeno Teorema de Fermat pode ser usado para dar um critério suficiente para decidir se um número é composto.
Lema 35.1 Assuma que \(n\geq 2\) é um número natural. Se \(b^{n-1}\not\equiv 1\pmod n\) para algum \(b\in\{2,\ldots,n-2\}\), então \(n\) é um número composto
Observe que a congruência \(b^{n-1}\equiv 1\pmod n\) pode ser checada para \(n\) muito grande usando o Algoritmo da Exponenciação Rápida.
Exemplo 35.1 Seja \[
n=100000000000000000039000000005700000000000000002223.
\] Queremos saber se \(n\) é um número primo ou ele é composto. Usando nossa implementação do algoritmo para calcular \(2^{n-1}\pmod n\), obtemos que \[
2^{n-1}\equiv 496813\ldots 506416 \neq 1\pmod n.
\] Portanto \(n\) é um número composto. É muito mais difícil verificar que de fato \[
n=100000000000000000039\cdot 10000000400000000000000000000057.
\]
Definição 35.1 Se \(n\geq 2\) e \(b^{n-1}\equiv 1\pmod n\) com algum \(b\in\{2,\ldots,n-1\}\), então o número \(n\) chama-se pseudoprimo para a base \(b\)
Exercício 35.1 Mostre para \(2\leq b<n\) que se \(n\) é pseudoprimo na base \(b\), então \(\mbox{mdc}(n,b)=1\)
Com a seguinte função em Python dá para verificar se um número é pseudoprimo para a base \(b\).
def PseudoPrimo( n, b ):return ExpModN( b, n-1, n ) ==1
Dado um número \(n\in\N\). Para testar se \(n\) é primo ou composto, podemos testar se \(n\) é pseudopromo para algumas bases \(b\in\{2,\ldots,n-1\}\). Se \(n\) não for pseudoprimo para uma destas bases, dá para concluir que \(n\) é composto. Caso contrário, o teste é inconclusivo.
Na primeira versão do teste, testamos se \(n\) for pseudoprimo para as bases entre \(2\) e \(2\log n\). O número \(2\log n\) é arbitrário e pode ser mudado, mas para um teste eficiente, o número de bases testadas precisa ser proporcional com o número de algarismos de \(n\); ou seja, proporcional com \(\log n\).
def TesteFermat( n ): d =2*int(log( n ))+1for b inrange( 2, d ):ifnot PseudoPrimo( n, b ):return"COMPOSTO"return"PROVAVELMENTE PRIMO"
Vamos testar quais são os números compostos entre 2 e um milhão que não são identificados como compostos usando este teste.
for n inrange( 2, 1000000 ):if TesteFermat( n ) =="PROVAVELMENTE PRIMO"andnot isprime( n ):print( n )252601294409399001410041488881512461
Em uma outra variante do teste de Fermat, podemos escolher as bases aleatoriamente entre \(2\) e \(2\log n\).
def TesteFermatRandom( n ): d =2*int(log( n ))+1for i inrange( 1, d ): b = random.randint( 2, n-2 )ifnot PseudoPrimo( n, b ):return"COMPOSTO"return"PROVAVELMENTE PRIMO"
Vamos identificar agora os números compostos entre 2 e 1000000 que não são identificados como compostos. Note que como o procedimento é aleatório, estes números serão diferentes cada vez que rodarmos a computação.
for n inrange( 5, 1000000 ):if TesteFermatRandom( n ) =="PROVAVELMENTE PRIMO"andnot isprime( n ):print( n )294409334153488881