Seja $n$ um número natural com $n\geq 5$ e seja $a\in\{2,\ldots,n-2\}$. Lembre que $n$ é dito pseudoprimo na base $a$ se $a^{n-1}\equiv 1\pmod n$. Observe que se $n$ for pseudoprimo na base $a$, então $a^n\equiv a\pmod n$.
Um número composto $n$ é dito número de Carmichael se $a^n\equiv a\pmod n$ para todo $a\in\{1,\ldots,n-1\}$.
Números de Carmichael são os mais prováveis de passarem no teste de primalidade de Fermat, pois se $n$ é de Carmichael, então $b^{n-1}\equiv 1\pmod n$ vale para qualquer base $b$ coprimo com $n$. Ou seja, $n$ será pseudoprimo para muitas bases.
O menor número de Carmichael é 561. Usando a definição de números de Carmichael, este fato não é fácil de verificar sem usar um computador. No entanto, a verificação pode ser feita sabendo que
\[
561=3\cdot 11\cdot 17.
\]
Seja $b\in\{1,\ldots,560\}$ arbitrário. Nós vamos mostrar que $b^{561}\equiv b\pmod{561}$. Esta congruéncia é equivalente ao fato que $561\mid (b^{561}-b)$. Para provar esta divisibilidade, basta verificar que $3$, $11$, e $17$ são divisores de $b^{561}-b$ para todo $b\in\{1,\ldots,560\}$.
Primeiro tratamos a afirmação que $17\mid (b^{561}-b)$; ou seja
\[
b^{561}\equiv b\pmod {17}.
\]
Se $17\mid b$, então os dois lados da congruência são congruentes com zero, então não há nada para fazer. Assuma que $17\nmid b$. Neste caso, o Pequeno Teorema de Fermat dá que $b^{16}\equiv 1\pmod{17}$ e isso implica que
\[
b^{560}=(b^{16})^{35}\equiv 1\pmod{17}.
\]
Obtemos assim que $b^{561}\equiv b\pmod{17}$ ou seja $17\mid( b^{561}-b)$.
Notando que $560=561-1$ é divisível por $3-1=2$ e por $11-1=10$, as divisibilidades $3\mid (b^{561}-b)$ e $11\mid (p^{561}-b)$ podem ser verificadas similarmente.
Observe que na conta acima os fatos cruciais sobre o número 561 foram os seguintes:
- o número 561 é livre de quadrado; ou seja, ele não é divisível por $p^2$ para nenhum primo $p$;
- se $p$ divide 561, então $p-1$ divide 560.
Acontece que estes dois fatos de fato são necessários e suficientes para um número ser de Carmichael.
- $n$ é livre de quadrado ($n$ não é divisível por $p^2$ para nenhum primo $p$);
- se $p$ é um primo que divide $n$, então $p-1$ divide $n-1$.
Vamos agora estudar um teste de primalidade que funciona melhor até com números de Carmichael.
Seja $n$ um número ímpar $n\geq 3$ e $b\in\{1,\ldots,n-1\}$. Seja $n-1=2^kq$ onde $k\geq 1$ e $q$ é ímpar. Se $n$ for primo, então ou $b^q\equiv 1\pmod n$, ou
\[
b^{2^iq}\equiv -1\pmod n\quad\mbox{para algum} \quad i=0,\ldots,k-1.
\]
\[
b^{n-1}=(b^{q})^{2^k}\equiv 1\pmod n.
\]
Isto quer dizer que, pelo menos um termo na sequência
\[
b^q,\ (b^q)^2,\ (b^q)^4,\ldots,(b^q)^{2^k}
\]
é congruente com $1$ módulo $n$. Assuma que $j\geq 0$ é o menor índice tal que
\[
(b^q)^{2^j}\equiv 1\pmod n.
\]
Se $j=0$, então $b^q\equiv 1\pmod n$ e a primeira alternativa do lema está válida. Se $j\geq 1$, então $(b^q)^{2^j}\equiv 1$ ímplica que
\[
(b^q)^{2^j}-1=((b^q)^{2^{j-1}}-1)((b^q)^{2^{j-1}}+1)
\]
é divisível por $n$. Como $n$ é primo, um dos fatores $(b^q)^{2^{j-1}}-1$ ou $(b^q)^{2^{j-1}}+1$ precisa ser divisível por $n$. Mas, pela minimalidade de $j$, o número $n$ não divide $(b^q)^{2^{j-1}}-1$, e isso significa que $(b^q)^{2^{j-1}}+1$ é divisível por $n$. Mas isso é equivalente a afirmação que $(b^q)^{2^{j-1}}\equiv -1\pmod n$.
O Teorema acima pode ser usado para criar um teste de primalidade um pouco mais sofisticada que o Teste de Fermat.
Algoritmo: TesteMiller Teste de de primalidade Miller
Input: Número natural $n$ ímpar e $b$ entre $2$ e $n-1$.
Claramente, a confiabilidade to Teste de Miller pode ser melhorada se executarmos o teste com várias bases $b$. É interessante notar que se a Hipótese Generalizada de Riemann (HGR) for verdadeira, o Teste de Miller pode ser usado para obter um teste de probabilidade que precisa de tempo polinomial.
Conjectura. Suponha que $n$ é um número composto ímpar. Então existe uma base $b\in\{2,\ldots,\lfloor 2(\log n)^2\rfloor\}$ tal que o número $n$ não passa no Teste de Miller na base $b$.
A veracidade da conjectura seria implicada pela veracidade da HGR que é considerada entre os problemas mais difíceis da matemática. De fato a Hipótese de Riemann aparece entre o Problemas do Prêmio Millennium e uma solução correta para este problema resultaria (além da fama eterna) um prêmio de um milhão de dólares.
A cota $\lfloor 2(\log n)^2\rfloor$ aparece no trabalho de Bach (1990). Assumindo a veracidade da HGR, o seguinte algoritmo determine se um número é primo ou composto.
Algoritmo: TesteMillerBach Teste de de primalidade Miller-Bach
Input: Número natural $n$ ímpar