Lemme de Gauss

Soit p un premier impair. Pour $n \in {\mathbb N}$, on appelle résidu minimal de n (modulo p) l'unique entier $n' \in ]-p/2,p/2[$tel que $n \equiv n'\ [p]$. Soit $m \in {\mathbb N}$, non multiple de p. On note $\mu$ le nombre d'entiers de $\{m,2m,\dots,\frac{p-1}{2}m\}$ dont le résidu minimal est strictement négatif.

Montrons que $\left(\frac{m}{p}\right)=(-1)^\mu$.

Posons $\lambda = \frac{p-1}{2} - \mu$. Considérons l'ensemble des résidus minimaux de

$$\{m,2m,\dots,\frac{p-1}{2}m\}.$$

Soient $r_1,\dots, r_\lambda$ les résidus minimaux positifs et $-r_1',\dots, -r_\mu'$ les résidus minimaux strictement négatifs. Comme les éléments de $\{m,2m,\dots,\frac{p-1}{2}m\}$ ne sont pas congrus deux à deux, les r_i sont distincts deux à deux. Il en va de même des r_i'. Montrons par l'absurde que pour tout $(i,j), r_i \not = r_j'$. Soient donc a et b dans $\{1, 2, \dots, (p-1)/2\}$ tels que $am \equiv r_i = r_j' \equiv -bm\ [p]$. Alors $0\equiv am+bm \equiv (a+b)m\ [p]$. p ne divisant pas m, p divise a+b ce qui est impossible car 0<a+b<p. Ainsi, $\{r_1, r_2, \dots, r_\lambda, r_1', r_2', \dots, r_\mu'\}= \{1, 2, \dots, \frac{p-1}{2}\}$.
On peut donc écrire modulo p :
$m.2m.3m\dots\frac{p-1}{2}.m \equiv (-1)^\mu r_1 r_2 \dots r_\lambda. r_1' r_2' \dots r_\mu' \equiv (-1)^\mu \frac{p-1}{2} !$

Comme p ne divise pas $\frac{p-1}{2} !$, il vient : $m^{\frac{p-1}{2}} \equiv (-1)^\mu\ [p]$ donc, d'après le critère d'Euler :

$$\left(\frac{m}{p}\right)= (-1)^\mu.$$

Le lemme de Gauss peut être utilisé pour déterminer les nombres premiers pour lesquels un entier préalablement choisi est un carré. C'est ce que nous allons faire avec les entiers 2 et -3 pour obtenir quelques formules, souvent appelées ``complémentaires''.