Définition Soit un entier. Une classe
est un résidu quadratique modulo si
pour une classe . Dans le cas
contraire, la classe est un non-résidu quadratique.
Exemples.Dressons les listes des résidus quadratiques
modulo quelques nombres premiers
Notons qu'il y a résidus quadratiques pour
chacun de ces nombres premiers et que est un résidu
quadratique pour .
Lemme
Soit un nombre premier impair.
a)
Parmi les éléments de
la
moitié exactement sont des résidus quadratiques.
a)
Pour tout
on a
.
On
si et seulement si est un
résidu quadratique modulo .
b)
La classe de est un résidu quadratique modulo si
et seulement si
.
Exemple 57
Le nombre est premier et congru à modulo .
Donc n'est pas résidu quadratique modulo . Par contre,
à l'aide de l'algorithme de calcul rapide
des puissances, on vérifie aisément que
.
Donc est un résidu quadratique modulo .
Démonstration. a) Nous savons que
est isomorphe
à
. Or ce dernier groupe contient exactement classes
multiples de .
b) Nous avons
d'après le petit théorème de Fermat ().
Donc
(car l'équation admet
exactement solutions dans
, d'après ).
Si ,
alors
modulo , par le petit
théorème de Fermat. Réciproquement, si
modulo , alors si est un générateur de
, nous avons
pour un
d'après le lemme (). Donc
est un carré.
c) D'après a), la classe de est un résidu quadratique
ssi
, c'est-à-dire que est pair ou
encore que vérifie
.
Théorème [Conjecture d'Euler] Soit un entier non nul et
un nombre premier impair. Le fait que soit résidu quadratique
modulo ou non ne dépend que de la classe de modulo .
Remarque 58
La conjecture, due à Euler, fut démontrée pour
la première fois par C. F. Gauss en 1796 sous le nom de
`théorème d'or'. Nous allons donner la démonstration
dans une section ultérieure.
Exemples.Nous avons déjà vu que est un
carré modulo
si et seulement si est congru à modulo , ou encore
modulo .
D'après le théorème, le fait que soit un carré modulo
ne dépend que de la classe de modulo . Or est
non résidu quadratique pour et , il est résidu quadratique
pour () et pour (). Donc est un
carré modulo ssi
.
Nous verrons plus tard que le calcul des classes de nombres premiers
modulo lesquels est un résidu quadratique peut toujours
se ramener à et .