Critère de primalité de Fermat : Montrer que $n$ est composé si et seulement s'il existe un entier $a$ tel que $1 < a < n$ et $a^{n-1} \not\equiv 1 \pmod n$. (Un tel $a$ s'appelle un témoin de Fermat. Il fournit un certificat de non-primalité pour $n$.)