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.