Les résidus quadratiques et la loi de réciprocité
Modulo 7, les carrés sont 1, 2 et 4 : l'équation x² ≡ 3 n'a pas de solution, mais x² ≡ 2 en a deux (3 et 4). Savoir quels nombres sont des carrés modulo p semble demander d'essayer toutes les valeurs. La loi de réciprocité quadratique, que Gauss appelait le « théorème d'or », permet de répondre presque sans calcul, en échangeant les rôles des deux nombres premiers. Cinq planches pour la comprendre, la démontrer par un dessin et s'en servir.
Vue d'ensemble
Soit p un nombre premier impair. Un entier a non divisible par p est un résidu quadratique modulo p si x² ≡ a (mod p) a une solution, et un non-résidu sinon. Legendre résume cela par un symbole :
(a/p) = +1 si a est un carré modulo p, −1 sinon, et 0 si p divise a.
| Résultat | Énoncé |
|---|---|
| Critère d'Euler | (a/p) ≡ a(p−1)/2 (mod p) |
| Multiplicativité | (ab/p) = (a/p)(b/p) : le produit de deux non-carrés est un carré |
| Premier complément | (−1/p) = +1 exactement quand p ≡ 1 (mod 4) |
| Second complément | (2/p) = +1 exactement quand p ≡ ±1 (mod 8) |
| Réciprocité | (p/q)(q/p) = (−1)(p−1)/2 · (q−1)/2 : les deux symboles sont égaux, sauf si p et q sont tous deux ≡ 3 (mod 4) |
Les carrés modulo p : exactement la moitié
Combien de nombres sont des carrés modulo un nombre premier p ?
Élevons au carré 1, 2, …, p − 1. Comme x² = (−x)² et que −x ≡ p − x, les carrés vont par paires : x et p − x ont le même carré. Ils ne peuvent pas coïncider davantage, car x² ≡ y² signifie que p divise (x − y)(x + y), donc x ≡ ±y (lemme d'Euclide). Il y a donc exactement (p − 1)/2 résidus quadratiques, et autant de non-résidus.
Le critère d'Euler et le symbole de Legendre
Peut-on reconnaître un carré sans chercher sa racine ?
Par le petit théorème de Fermat, ap−1 ≡ 1, donc b = a(p−1)/2 vérifie b² ≡ 1, et b ≡ ±1. Euler a montré que b ≡ +1 exactement quand a est un carré : si a ≡ x², alors b ≡ xp−1 ≡ 1. Une seule exponentiation rapide suffit donc pour trancher. On en déduit aussi la multiplicativité : (ab/p) = (a/p)(b/p). Un résidu fois un résidu donne un résidu, et un non-résidu fois un non-résidu aussi, comme « moins par moins donne plus ».
−1, 2 et le lemme de Gauss
Quand −1 est-il un carré modulo p ? Et 2 ?
Le critère d'Euler donne (−1/p) = (−1)(p−1)/2 : −1 est un carré modulo p exactement quand p ≡ 1 (mod 4). C'est la clé du théorème des deux carrés de Fermat : un nombre premier impair s'écrit a² + b² exactement quand p ≡ 1 (mod 4). Pour 2, Gauss a trouvé une méthode de comptage : on regarde les restes de a, 2a, 3a, …, ((p−1)/2)·a modulo p, et l'on compte ceux qui dépassent p/2. Si ce nombre μ est pair, a est un carré ; s'il est impair, non. Pour a = 2, le compte ne dépend que de p modulo 8.
La loi de réciprocité, démontrée par un dessin
Pourquoi (p/q) et (q/p) sont-ils liés, alors que l'un parle de carrés modulo q et l'autre modulo p ?
Eisenstein (1844) a transformé le lemme de Gauss en un comptage de points. On montre que (q/p) = (−1)S, où S = ⌊q/p⌋ + ⌊2q/p⌋ + … + ⌊((p−1)/2)q/p⌋ est le nombre de points entiers situés sous la diagonale du rectangle de côtés p/2 et q/2. Symétriquement, (p/q) = (−1)T, où T compte les points au-dessus. Aucun point n'est sur la diagonale, car p et q sont premiers entre eux. Donc S + T est le nombre total de points du rectangle, soit (p − 1)/2 × (q − 1)/2. C'est toute la démonstration.
Signature : calculer, extraire, sommer
La réciprocité permet de calculer un symbole aussi vite qu'un PGCD ; d'autres méthodes trouvent la racine carrée elle-même ; et une somme de Gauss cache √p.
Pour savoir si 1 001 est un carré modulo 9 907, faut-il factoriser 1 001 = 7 × 11 × 13 ? Non : Jacobi (1837) étend le symbole à tout dénominateur impair, et la réciprocité reste vraie. On peut alors retourner la fraction comme dans l'algorithme d'Euclide, en sortant les facteurs 2 grâce au second complément. Le calcul se fait en quelques étapes, sans jamais factoriser.
Savoir qu'une racine existe ne la donne pas. Si p ≡ 3 (mod 4), c'est facile : x = a(p+1)/4 convient. Sinon, l'algorithme de Tonelli (1891), amélioré par Shanks (1973), écrit p − 1 = Q·2S, prend un non-résidu z, puis corrige une approximation pas à pas. On s'en sert en cryptographie sur les courbes elliptiques, pour retrouver un point à partir de son abscisse.
Additionnons les racines p-ièmes de l'unité e2iπa/p, chacune affectée du signe (a/p). Le résultat, la somme de Gauss, a toujours pour module √p exactement. Elle vaut +√p si p ≡ 1 (mod 4) et i√p si p ≡ 3 (mod 4). Gauss connaissait le module, mais il lui a fallu quatre ans, de 1801 à 1805, pour démontrer le signe. C'est d'ailleurs l'une de ses huit preuves de la loi de réciprocité qui passe par ces sommes.
Une brève histoire
En résumé
Moitié carrés, moitié non
Modulo p premier, exactement (p − 1)/2 nombres sont des carrés. Le critère d'Euler les reconnaît par une seule puissance, et le symbole de Legendre est multiplicatif.
Le théorème d'or
(p/q) et (q/p) sont égaux, sauf si p et q sont tous deux ≡ 3 (mod 4). Eisenstein le démontre en comptant des points de part et d'autre d'une diagonale.
Des outils de calcul
Le symbole de Jacobi se calcule comme un PGCD, Tonelli-Shanks extrait la racine, et la somme de Gauss relie les carrés modulo p à √p.
Pour aller plus loin
Les formes quadratiques. Savoir quels nombres premiers s'écrivent x² + ny² (pour n = 1, 2, 3…) prolonge le théorème des deux carrés : la réponse fait intervenir les symboles (−n/p), puis la théorie des corps de classes.
Les codes correcteurs. Les résidus quadratiques modulo p définissent des codes correcteurs d'erreurs (codes de résidus quadratiques), et les matrices de Paley, utilisées en conception d'expériences.
Liens. Fermat, Euler et les restes chinois, PGCD et algorithme d'Euclide, décomposition en facteurs premiers, théorie algébrique des nombres (décomposition des nombres premiers dans ℤ[i] et ℤ[√d]).