Priemgetal কী?

Voorbeeld 6.24 (De omkering van Fermat faalt: $341$)

De kleine stelling van Fermat levert een goedkope toets op samengesteldheid: is $a^{n-1} \not\equiv 1 \pmod n$ voor een zekere $a$ die relatief priem is met $n$, dan is $n$ niet priem. Zou de toets ook primaliteit kunnen waarborgen? Nee: neem $n = 341 = 11 \times 31$, samengesteld, en $a = 2$. Omdat $2^{10} = 1024 = 3 \times 341 + 1$, is

het samengestelde getal $341$ doorstaat de toets van Fermat voor het grondtal $2$ (het is het kleinste zulke pseudopriemgetal). Het grondtal $3$ ontmaskert het ($3^{340} \not\equiv 1$), en in de praktijk draait een primaliteitstoets daarom op verscheidene grondtallen, plus verfijningen — de industriële versies van dit idee zijn wat de grote priemgetallen uit Opmerking 6.27 waarborgt. Moraal: een implicatie en haar omkering leiden gescheiden levens (Opmerking 1.10), zelfs bij stellingen.