Un générateur du groupe des inversibles n'est pas un résidu quadratique. Réciproquement, si x n'est pas résidu quadratique, cela signifie que
Montrons que 3, 5 et 7 sont des générateurs de , si
.
D'après la loi de réciprocité quadratique, si , alors 5
est un carré modulo p si et seulement si p est un
carré modulo 5. Or
et 2 n'est pas un
carré modulo 5.
De la même manière, on montre que si
, alors 7 est un
carré modulo p si et seulement si p est un carré modulo 7.
Or p est congru à 3 ou 5 modulo 7 et les seuls carrés modulo 7 sont 1, 2
et 4.
Montrons finalement le critère de Pépin :
Supposons la congruence vérifiée. On a ; l'ordre
de 3 modulo p est exactement p-1. L'anneau
est donc un corps.
Réciproquement, supposons p premier ; tout revient à voir que 3 n'est pas
un carré modulo p. On remarque que
n'est pas un carré modulo 3, et donc, comme ci-dessus, 3 n'est un
carré modulo p (sauf, bien sûr, si p=3).
On fait également appel aux résidus quadratiques pour montrer la première
implication [Naudin] du test de Lucas-Lehmer sur les nombres de Mersenne :
un nombre de Mersenne Mn=2n-1 () est premier
où
L0=4 et
.
Notons qu'on a ainsi obtenu les 36 nombres premiers Mq pour q= 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269 et 2976221. M2976221 est en outre le plus grand nombre premier actuellement connu (c'est-à-dire en septembre 1997, voir le site web cité ci-dessous pour éviter de colporter des informations surannées). Il arrive souvent que le record du ``plus grand nombre premier connu'' soit battu par des nombres de Mersenne, de par la facilité d'implémentation du test (quoique ce dernier nécessite, pour des nombres aussi grands, l'utilisation de cet outil puissant qu'est la transformée de Fourier rapide, théorie développée en 1965 par Cooley et Tuckey puis par Schönhage et Strassen). Soyons assurés que le prochain record sera également un nombre de Mersenne et qu'il sera trouvé, comme les derniers, par D. Slowinski sur des super-ordinateurs Cray ou par le projet international accessible sur Internet (www.mersenne.org) où tout un chacun peut offrir un peu de sa puissance CPU.