Exemple d'utilisation

Prenons le nombre $341 = 11 \times 31$ :

$2^{340} \equiv 1 \;(mod\; 341)$.

$341$ n'est pas premier mais vérifie le critère de Fermat pour $a = 2$.

Posons-nous la question : $2^{170} \equiv \pm 1 \;(mod\; 341)$ ?

(en effet si 341 est premier, $\frac{\mathbb{Z}}{341\mathbb{Z}}$ est un corps et $2^{170} \equiv \pm 1 \;(mod\; 341)$).

Si $2^{170} \equiv 1 \;(mod\; 341)$ alors demandons-nous $2^{85} \equiv \pm 1 \;(mod\; 341)$ ? etc ...

Raccourci :

on a $2^5 \equiv -1 \;(mod\; 11)$ et $2^5 \equiv 1 \;(mod\; 31)$

d'où $2^{85} \equiv -1 \;(mod\; 11)$ et $2^{85} \equiv 1 \;(mod\; 31)$

d'où $2^{170} \equiv 1 \;(mod\; 11)$ et $2^{170} \equiv 1 \;(mod\; 31)$

d'où $2^{170} \equiv 1 \;(mod\; 341)$.

Or si $2^{85} \equiv -1 \;(mod\; 341)$ on aurait

$2^{85} \equiv -1 \;(mod\; 11)$ et $2^{85} \equiv -1 \;(mod\; 31)$ (de même pour $2^{85} \equiv 1 \;(mod\; 341)$);

donc 341 n'est pas premier.