Lemme de Gauss (théorie des nombres)

Pour les articles homonymes, voir Théorème de Gauss.

Le lemme de Gauss en théorie des nombres donne une condition pour qu'un entier soit un résidu quadratique. Il a été introduit et démontré par Gauss dans ses preuves de la loi de réciprocité quadratique^[1],[2] et est utilisé dans plusieurs des nombreuses preuves ultérieures de cette loi^[3].

Énoncé

Soient p un nombre premier impair et a un entier non divisible par p.

On considère les entiers

$a,2a,3a,\dots,\frac{p-1}{2}a$

et leurs plus petits résidus positifs modulo p.

Parmi ces (p − 1) / 2 entiers distincts compris entre 1 et p − 1, soit n le nombre de ceux qui sont plus grands que p / 2. Alors

$\left(\frac ap\right) = (-1)^n$,

où $\left(\frac ap\right)$ est le symbole de Legendre.

Application

Les deux « lois complémentaires » de la loi de réciprocité quadratique se déduisent du lemme de Gauss par simple évaluation de n en fonction de p pour a=-1 et a=2.

Preuve

Une preuve assez simple de ce lemme peut être déduite du principe utilisé pour la démonstration du petit théorème de Fermat. Pour cela, évaluons modulo p le produit suivant :

$Z = a \cdot 2a \cdot 3a\ldots\frac{p-1}2a,$

de deux manières différentes.

Premièrement, ce produit vaut :

$Z = a^{(p-1)/2} \left(1 \cdot 2 \cdot 3\ldots\frac{p-1}2 \right).$

La seconde façon d'évaluer Z est plus délicate. Si x, compris entre 1 et p-1, est le résidu modulo p d'un entier y, définissons la « valeur absolue » de y comme

$|y| = \begin{cases} x & \mbox{si } 1 \leq x \leq \frac{p-1}2, \\p-x & \mbox{si } \frac{p+1}2 \leq x \leq p-1. \end{cases}$

Comme n dénombre les multiples ka dont le résidu se trouve dans le second intervalle, on a :

$Z\equiv(-1)^n \left(|a| \cdot |2a| \cdot |3a|\ldots\left|\frac{p-1}2a\right|\right)\pmod p.$

Maintenant, observons que les valeurs |ra| sont distinctes pour r = 1, 2, … , (p−1)/2. En effet, si |ra| = |sa|, alors ra ≡ ±sa (mod p), d'où (comme a est inversible modulo p) r ≡ ±s (mod p), donc r et s sont égaux (car ils appartiennent tous deux à l'intervalle 1 ≤ r ≤ (p−1)/2). Mais il y en a exactement (p−1)/2, donc cette suite est une permutation des entiers 1, 2, ..., (p−1)/2. On obtient :

$Z\equiv(-1)^n \left(1 \cdot 2 \cdot 3\ldots\frac{p-1}2\right)\pmod p.$

En comparant avec notre premier calcul, on peut supprimer les facteurs inversibles modulo p :

$1 \cdot 2 \cdot 3\ldots\frac{p-1}2$

ce qui nous donne

$a^{(p-1)/2}\equiv(-1)^n\pmod p.$

Ceci est le résultat souhaité, car d'après le critère d'Euler, la partie de gauche n'est qu'une réécriture modulo p du symbole de Legendre (a/p).

Autre preuve, par la théorie du transfert

De par sa définition, l'application qui à a associe (-1)ⁿ est un morphisme de transfert du groupe abélien G = Z/pZ* dans le sous-groupe Q = {-1,+1}. D'après le théorème d'évaluation du transfert, on en déduit que l'image de a par ce morphisme est égale à a^m où m désigne l'indice de Q dans G, c'est-à-dire m = (p - 1)/2, ce qui conclut.

Notes et références

Notes

1. ↑ (la) C. F. Gauss, « Theorematis arithmetici demonstratio nova », dans Comment. Soc. regiae sci. Göttingen, XVI, 1808
2. ↑ (la) C. F. Gauss, « Theorematis fundamentalis in doctrina de residuis quadraticis demonstrationes et amplicationes novae », 1818
3. ↑ (en) Franz Lemmermeyer (de), Reciprocity Laws: from Euler to Eisenstein, Springer, 2000 (ISBN 978-3-540-66957-9), chap. 1 

Références

• (en)/(en) Cet article est partiellement ou en totalité issu des articles intitulés en anglais « Gauss lemma » (voir la liste des auteurs) et en anglais « Gauss's lemma (number theory) » (voir la liste des auteurs)
• (en) Tom M. Apostol, Introduction to Analytic Number Theory, vol. 1, Springer, 1976 (ISBN 978-0-387-90163-3) 

Voir aussi

Article connexe

Lemme de Zolotarev

Lien externe

Une démonstration en ligne