Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
71 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 next up previous contents
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 $ n$ si $ a= b^2$ pour une classe $ b$. Dans le cas contraire, la classe $ a$ 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 $ (p-1)/2$ résidus quadratiques pour chacun de ces nombres premiers et que $ -1$ est un résidu quadratique pour $ 5,13,29$.

Lemme Soit $ p=2 l+1$ un nombre premier impair.

a)
Parmi les $ 2l$ é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 $ a$ est un résidu quadratique modulo $ p$.
b)
La classe de $ -1$ est un résidu quadratique modulo $ p$ si et seulement si $ p\equiv 1\;(4)$.

Exemple 57   Le nombre $ 2011$ est premier et congru à $ 3$ modulo $ 4$. Donc $ -1$ n'est pas résidu quadratique modulo $ 2011$. Par contre, à l'aide de l'algorithme de calcul rapide des puissances, on vérifie aisément que $ 1848^{1005} \equiv 1\; (2011)$. Donc $ 1848$ est un résidu quadratique modulo $ 2011$.


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 $ l$ classes multiples de $ 2$.

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 $ x^2=1$ admet exactement $ 2$ solutions dans $ {\mbox{\bf Z}}/p{\mbox{\bf Z}}$, d'après [*]).

Si $ a= b^2$, alors $ a^k=b^{2 k}= b^{p-1}=1$ modulo $ p$, par le petit théorème de Fermat. Réciproquement, si $ a^l= 1$ modulo $ p$, alors si $ g$ 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 $ a$ est un carré.

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

$ \surd$

Théorème [Conjecture d'Euler] Soit $ a$ un entier non nul et $ p$ un nombre premier impair. Le fait que $ a$ soit résidu quadratique modulo $ p$ ou non ne dépend que de la classe de $ p$ modulo $ 4a$.

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 $ -1$ est un carré modulo $ p$ si et seulement si $ p$ est congru à $ 1$ modulo $ 4$, ou encore modulo $ -4=4(-1)$.

D'après le théorème, le fait que $ 2$ soit un carré modulo $ p$ ne dépend que de la classe de $ p$ modulo $ 8$. Or $ 2$ est non résidu quadratique pour $ 3$ et $ 5$, il est résidu quadratique pour $ 7$ ($ 4^2=2$) et pour $ 17$ ($ 6^2=2$). Donc $ 2$ est un carré modulo $ p$ ssi $ p\equiv\pm 1 \;(8)$.

Nous verrons plus tard que le calcul des classes de nombres premiers $ p$ modulo lesquels $ a$ est un résidu quadratique peut toujours se ramener à $ a=2$ et $ a=-1$.


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

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page