Número primo কী?

Exemplo 6.24 (A recíproca de Fermat falha: $341$)

O pequeno teorema de Fermat dá um teste barato de composicionalidade: se $a^{n-1} \not\equiv 1 \pmod n$ para algum $a$ primo com $n$, então $n$ não é primo. O teste poderia também certificar a primalidade? Não: tome $n = 341 = 11 \times 31$, composto, e $a = 2$. Como $2^{10} = 1024 = 3 \times 341 + 1$,

o composto $341$ passa no teste de Fermat na base $2$ (é o menor pseudoprimo desse tipo). A base $3$ o desmascara ($3^{340} \not\equiv 1$), e o teste prático de primalidade, portanto, roda o teste em várias bases, com refinamentos — as versões industriais dessa ideia são o que certifica os grandes primos da Observação 6.27. Moral: uma implicação e a sua recíproca vivem vidas separadas (Observação 1.10), mesmo para teoremas.