Posons . Considérons l'ensemble des
résidus minimaux de {m, 2m, (p-1)/2 m}.
Soient les résidus minimaux positifs et les résidus minimaux strictement négatifs.
Comme les éléments de ne sont pas congrus
deux à deux, les ri sont distincts deux à deux.
Il en va de même des ri'. Montrons par l'absurde que pour tout
. Soient donc a et b dans
tels que .
Alors . p ne divisant pas m, p
divise a+b ce qui est impossible car 0<a+b<p.
Ainsi, .
On peut donc écrire modulo p :
Comme p ne divise pas , il vient : donc, d'après le critère d'Euler :
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''.