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.
Seja $n\geq 2$ um número natural composto. Então $n$ é um número de Carmichael (ou seja, $b^n\equiv b\pmod n$ para todo $b\in\{1,\ldots,n-1\}$) se e somente se as seguintes propriedades são válidas:
- $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$.
Se $p_i\mid a$, então $p_i\mid a^n-a$. Se $p_i\nmid a$, então o Pequeno Teorema de Fermat implica que $a^{p_i-1}\equiv 1\pmod{p_i}$. Pela condição 1., temos que $p-1\mid n-1$; ou seja $n=q(p_i-1)+1$ com algum $q\in\Z$. Logo
\[
a^n=a^{q(p_i-1)+1}=(a^{p_i-1})^qa\equiv a\pmod{p_i}.
\]
Mas isso implica que $p_i\mid a^n-a$. Como isso é verdadeiro para todo $i\in\{1,\ldots,k\}$, obtemos que $n\mid a^n-a$; ou seja $a^n\equiv a\pmod n$.
Agora consideremos a ida. Assuma que $n\in\N$ é um número de Carmichael. Promeiro provaremos afirmação 1. Assuma por contradição que $p^2\mid n$ com algum primo $p$. Como $n$ é Carmichael, $p^n\equiv p\pmod n$, ou seja $n\mid p^n-p$. Mas isso implica que
\[
p^2\mid p^n-p=p(p^{n-1}-1)
\]
o que é impossível, pois o primeiro fator no lado direito é divisível por $p$, mas não por $p^2$, enquanto o segundo fator não é divisível por $p$.
Agora assuma que $p$ é um primo tal que $p\mid n$. Precisamos provar que $p-1\mid n-1$. O Teorema da Raiz Primitiva implica que existe $a\in\Z$ tal que $|a|_p=p-1$ (ou seja, $a^{p-1}\equiv 1\pmod p$, mas $a^k\not\equiv 1\pmod p$ para todo $k\in\{1,\ldots,p-2\}$). Como $n$ é Carmichael, temos que $a^n\equiv a\pmod n$, e assim $a^n\equiv a\pmod p$ (como $p\mid n$). Mas $a$ é invertível módulo $p$ e assim $a^{n-1}\equiv 1\pmod p$ também segue. Isso implica que
\[
p-1=|a|_p\mid n-1
\]
e é isso que nós queremos provar.