Lemme de Gauss (théorie des nombres)

Soient ${\displaystyle p}$ un nombre premier impair et ${\displaystyle a}$ un entier non divisible par ${\displaystyle p}$. Alors

${\displaystyle \left({\frac {a}{p}}\right)=(-1)^{n}}$,

où ${\displaystyle \left({\frac {a}{p}}\right)}$ est le symbole de Legendre et ${\displaystyle n}$ est défini de la façon suivante :

On considère les entiers ${\displaystyle a,2a,3a,\dots ,{\frac {p-1}{2}}a}$ et leurs plus petits résidus positifs ${\displaystyle {\bmod {p}}}$.

Parmi ces ${\displaystyle (p-1)/2}$ entiers distincts compris entre ${\displaystyle 1}$ et ${\displaystyle p-1}$, ${\displaystyle n}$ est le nombre de ceux qui sont plus grands que ${\displaystyle p/2}$.

ou encore, de façon équivalente :

${\displaystyle n}$ est le nombre d'entiers négatifs parmi ${\displaystyle r(a),r(2a),\ldots ,r\left({\frac {p-1}{2}}a\right)}$, en désignant par ${\displaystyle r(k)}$, pour tout entier ${\displaystyle k}$, l'unique entier de l'intervalle ${\displaystyle \left]-p/2,p/2\right[}$ congru à ${\displaystyle k{\bmod {p}}}$.

La deuxième « loi complémentaire » de la loi de réciprocité quadratique se déduit du lemme de Gauss[4].

Une preuve assez simple de ce lemme[5] utilise le même principe que l'une des démonstrations du petit théorème de Fermat, en évaluant de deux façons le produit modulo p de ces (p – 1)/2 entiers.

De par sa définition, l'application qui à a associe (–1)ⁿ est un morphisme de transfert du groupe abélien G = (ℤ/pℤ)* 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.

Lemme de Zolotarev