Critère de Pépin sur les nombres de Fermat

Soit p=F_n=2²ⁿ+1 un nombre de Fermat premier, avec $n \geq 2$.
Montrons qu'un élément est un générateur de $U({\mathbb F}_p)$ (l'ensemble des inversibles) si et seulement s'il n'est pas résidu quadratique.

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

$$-1=\left(\frac{x}{p}\right) \equiv x^\frac{p-1}{2} \ [p]$$

et puisque l'ordre de x divise une puissance de 2, cet ordre est exactement p-1.

Montrons que 3, 5 et 7 sont des générateurs de $U({\mathbb F}_p)$, si $n \geq 2$.

D'après la loi de réciprocité quadratique, si $p \not = 5$, alors 5 est un carré modulo p si et seulement si p est un carré modulo 5. Or $p=4^{2^{n-1}}+1 \equiv 2 \ [5]$ et 2 n'est pas un carré modulo 5. De la même manière, on montre que si $p\not =3$, 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 :

$$p=F_n {\rm \ est premier \ } \Longleftrightarrow 3^\frac{p-1}{2}\equiv -1 \ [F_n].$$

Supposons la congruence vérifiée. On a $3^{p-1}\equiv 1 \ [p]$ ; l'ordre de 3 modulo p est exactement p-1. L'anneau ${\mathbb Z}/p{\mathbb Z}$ est donc un corps. Réciproquement, supposons p premier ; tout revient à voir que 3 n'est pas un carré modulo p. On remarque que $p\equiv 2 \ [3]$ 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 M_n=2ⁿ-1 ($n \geq 3$) est premier $\Longleftrightarrow L_{q-2} \equiv 0 \ [M_q]$ où L₀=4 et $L_{i+1}=L_i^2-2 \ [M_q]$.

Notons qu'on a ainsi obtenu les 36 nombres premiers M_q 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. M_2976221 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.