A lire

Deug/Prépa

Licence

Agrégation
A télécharger

Télécharger

253 personne(s) sur le site en ce moment

E. Cartan

A lire

Articles

Math/Infos

Récréation
A télécharger

Télécharger

Théorème de Cantor-Bernstein

Théo. Sylow

Théo. Ascoli

Théo. Baire

Loi forte grd nbre

Nains magiques

Résidus quadratiques

suivant: Le symbole de Legendre monter: bad précédent: L'indicatrice de Carmichael Table des matières

Résidus quadratiques

Définition Soit $n\geq 2$ un entier. Une classe $a\in({\mbox{\bf Z}}/n{\mbox{\bf Z}})^*$ 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

$\displaystyle 2$	$\displaystyle :$	$\displaystyle 1$
$\displaystyle 3$	$\displaystyle :$	$\displaystyle 1$
$\displaystyle 5$	$\displaystyle :$	$\displaystyle 1, 4$
$\displaystyle 7$	$\displaystyle :$	$\displaystyle 1, 2, 4$
$\displaystyle 11$	$\displaystyle :$	$\displaystyle 1,3,4,5,9$
$\displaystyle 13$	$\displaystyle :$	$\displaystyle 1,3,4,9,10,12$
$\displaystyle 17$	$\displaystyle :$	$\displaystyle 1,2,4,8,9,13,15,16$
$\displaystyle 19$	$\displaystyle :$	$\displaystyle 1,4,5,6,7,9,11,16,17$
$\displaystyle 23$	$\displaystyle :$	$\displaystyle 1,2,3,4,6,8,9,12,13,16,18$
$\displaystyle 29$	$\displaystyle :$	$\displaystyle 1,4,5,6,7,9,13,16,20,22,23,24,25,28$

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 $({\mbox{\bf Z}}/p{\mbox{\bf Z}})^*$ la moitié exactement sont des résidus quadratiques.
a): Pour tout $a\in({\mbox{\bf Z}}/p{\mbox{\bf Z}})^*$ on a $a^l\equiv \pm 1\; (p)$ . On $a^l\equiv 1\; (p)$ si et seulement si est un résidu quadratique modulo .
b): La classe de est un résidu quadratique modulo si et seulement si $p\equiv 1\;(4)$ .

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 $1848^{1005} \equiv 1\; (2011)$ . Donc

est un résidu quadratique modulo

Démonstration. a) Nous savons que $({\mbox{\bf Z}}/p{\mbox{\bf Z}})^*$ est isomorphe à ${\mbox{\bf Z}}/2l{\mbox{\bf Z}}$ . Or ce dernier groupe contient exactement classes multiples de .

b) Nous avons $(a^l)^2\equiv a^{p-1} \equiv 1\;(p)$ d'après le petit théorème de Fermat (). Donc $a^l\equiv \pm 1\; (p)$ (car l'équation admet exactement solutions dans ${\mbox{\bf Z}}/p{\mbox{\bf Z}}$ , d'après ).

Si , alors $a^k=b^{2 k}= b^{p-1}=1$ modulo , par le petit théorème de Fermat. Réciproquement, si modulo , alors si est un générateur de $({\mbox{\bf Z}}/p{\mbox{\bf Z}})^*$ , nous avons $a=g^{2 k}$ pour un $k\in{\mbox{\bf Z}}$ d'après le lemme (). Donc est un carré.

c) D'après a), la classe de est un résidu quadratique ssi $(-1)^l \equiv 1\; (p)$ , c'est-à-dire que est pair ou encore que vérifie $p\equiv 1\;(4)$ .

$\surd$

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 $p\equiv\pm 1 \;(8)$ .