\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.
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.
\[
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.
\]
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 ))+1
for b in range( 2, d ):
if not 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 in range( 2, 1000000 ):
if TesteFermat( n ) == "PROVAVELMENTE PRIMO" and not isprime( n ):
print( n )
252601
294409
399001
410041
488881
512461
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 ))+1
for i in range( 1, d ):
b = random.randint( 2, n-2 )
if not 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 in range( 5, 1000000 ):
if TesteFermatRandom( n ) == "PROVAVELMENTE PRIMO" and not isprime( n ):
print( n )
294409
334153
488881