Voir la source de Résidu quadratique

{{ébauche|mathématiques}}
En [[mathématiques]], plus précisément en [[arithmétique modulaire]], un [[entier naturel]] {{mvar|q}} est un '''résidu quadratique''' [[congruence sur les entiers|modulo]] {{mvar|n}} s'il possède une [[racine carrée]] en [[arithmétique modulaire]] de module {{mvar|n}}. Autrement dit, {{mvar|q}} est un résidu quadratique modulo {{mvar|n}} s'il existe un entier {{mvar|x}} tel que :

:<math>{x^2}\equiv q\pmod n</math>.

Dans le cas contraire, on dit que {{mvar|q}} est un '''non-résidu quadratique''' modulo {{mvar|n}}

== Exemples ==
Par exemple :
*modulo 4, les résidus quadratiques sont les entiers congrus à 2{{2}} ≡ 0{{2}} = 0 ou à (±1){{2}} = 1. Les non-résidus quadratiques sont donc ceux congrus à 2 ou à 3 ;
*modulo 2, tout entier est un résidu quadratique ;
*modulo ''p'', tout multiple de ''p'' est un résidu quadratique. Pour cette raison, certains auteurs<ref>{{harvsp|Gauss|loc=§ 96 et 105}}.</ref>{{,}}<ref>{{Ouvrage|langue=en|auteur1=Kenneth Ireland|auteur2=[[Michael Rosen (mathématicien)|Michael Rosen]]|titre=A Classical Introduction to Modern Number Theory|éditeur=[[Springer Verlag|Springer]]|collection=[[Graduate Texts in Mathematics|GTM]]|numéro dans collection=84|année=1990|passage=50|lire en ligne=https://books.google.fr/books?id=jhAXHuP2y04C&pg=PA50}}.</ref> excluent les multiples de ''p'' de la définition et imposent même que ''p'' et ''q'' soient [[premiers entre eux]].

== Modulo un entier quelconque ==
Modulo un entier {{math|''n'' > 0}}, la classe de {{mvar|x}}{{2}} ne dépend que de celle de {{mvar|x}}, donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de {{mvar|x}}{{2}} par {{mvar|n}} en faisant varier {{mvar|x}} dans <math>\left\{0,1,\dots,n-1\right\}</math>, ou dans n'importe quel ensemble de {{mvar|n}} entiers consécutifs, comme <math>\left\{\left\lfloor\frac{-n}2\right\rfloor+1,\left\lfloor\frac{-n}2\right\rfloor+2,\dots,\left\lfloor\frac n2\right\rfloor\right\}</math> ({{c.-à-d.}} <math>\left\{-\frac n2+1,\dots,\frac n2\right\}</math> si {{mvar|n}} est pair et <math>\left\{-\frac{n-1}2,\dots,\frac{n-1}2\right\}</math> si {{mvar|n}} est impair).

On peut même se limiter à <math>x\in\left\{0,1,...,\left\lfloor\frac n2\right\rfloor\right\}</math>, puisque <math>\left(-x\right)^2=x^2</math>.

En outre, 0 et 1 sont toujours résidus quadratiques.

{{Exemple|
Le tableau ci-dessous des résidus quadratiques modulo 10 expose bien la symétrie et montre que l'on peut se restreindre à <math>x\in\{0,1,...,5\}</math>. 

<center><math>\begin{array}{|c|c|c|c||c|c|c|} x & -4&-3&-2&-1&0&1&2&3&4&5\\ \hline x^2&{\color{magenta} 6}&{\color{cyan} 9}&{\color{blue} 4} & {\color{green} 1}  & {\color{red} 0} & {\color{green} 1}&{\color{blue} 4}&{\color{cyan} 9}&{\color{magenta} 6}& {\color{brown}5}\end{array}</math></center>
}}
Soient {{mvar|a}} et {{mvar|b}} deux entiers premiers entre eux. Un entier {{mvar|x}} est un résidu quadratique {{math|mod ''ab''}} si (et bien sûr seulement si) <math>x</math> est un résidu quadratique à la fois {{math|mod ''a''}} et {{math|mod ''b''}}.

{{Démonstration|contenu=Si <math>x\equiv u^2\bmod a</math> et <math>x\equiv v^2\bmod b</math>, soit (par le [[théorème des restes chinois]]) un entier <math>w</math> tel que <math>w\equiv u\bmod a</math> et <math>w\equiv v\bmod b</math>. Alors, <math>x\equiv w^2\bmod a</math> et <math>x\equiv w^2\bmod b</math> donc (par le [[Lemme d'Euclide|lemme de Gauss]]) <math>x\equiv w^2\bmod{ab}</math>.}}

Cette propriété permet de ramener la détermination des résidus quadratiques modulo un entier quelconque à celle des résidus modulo les [[Nombre primaire|puissances de nombres premiers]] qui apparaissent dans [[Décomposition en produit de facteurs premiers|sa décomposition]].

== Modulo un [[nombre premier]] impair ==
Soit {{mvar|p}} un nombre premier impair. Pour tout entier {{mvar|n}}, le [[symbole de Legendre]] {{math|(''n''/''p'')}} vaut, par définition :
:<math>
\left(\frac np\right) = \begin{cases}\;\;\,0&\text{ si }n\text { est divisible par } p\\+1&\text{ si }n\text { n'est pas divisible par } p\text{ et est un résidu quadratique modulo } p\\-1&\text{ si }n\text { n'est pas un résidu quadratique modulo } p.\end{cases}</math>
D'après le [[critère d'Euler]], il est congru modulo {{mvar|p}} à {{math|''n''{{exp|(''p''–1)/2}}}}. Le [[Lemme de Gauss (théorie des nombres)|lemme de Gauss]] en fournit une autre expression.

La [[loi de réciprocité quadratique]] permet de calculer (–1/''p''), (2/''p'') et, si ''q'' est un autre nombre premier impair, (''q''/''p'') en fonction de (''p''/''q''). Elle fournit par exemple, pour un entier ''n'' donné, un critère sur le nombre premier ''p'' en termes de classes de congruence modulo 4''n'', qui détermine si {{mvar|n}} est un résidu quadratique modulo ''p''. Le [[théorème de la progression arithmétique]] permet<ref>{{Ouvrage|langue=en|auteur1=Steve Wright|titre=Quadratic Residues and Non-Residues|sous-titre=Selected Topics|éditeur=Springer|collection=Lecture Notes in Mathematics|numéro dans collection=2171|année=2016|arxiv=1408.0235|lire en ligne={{Google Livres|rxp_DQAAQBAJ|page=88}}}}, théorèmes 4.2 et 4.3, et {{Article|titre=Patterns of quadratic residues and nonresidues for infinitely many primes|revue=[[Liste des journaux scientifiques en mathématiques#J|J. Number Theory]]|vol=123|numéro=1|année=2007|p.=120-132|doi=10.1016/j.jnt.2006.06.003}}. Pour une généralisation simultanée de ces deux théorèmes, voir {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Résidus quadratiques#Exercice 4-16|cet ''exercice'' corrigé de la leçon « Introduction à la théorie des nombres »|début=}}</ref>{{,}}<ref name=boyer>{{Ouvrage|langue=fr|auteur1=Pascal Boyer|titre=Petit compagnon des nombres et de leurs applications|lieu=Paris|éditeur=Calvage et Mounet|année=2019|pages totales=648|passage=47-49|isbn=978-2-916352-75-6|partie=Arithmétique de ℤ|numéro chapitre=I.3.2|titre chapitre=Résidus quadratiques : applications}}.</ref> d'en déduire que si {{mvar|n}} n'est pas un [[carré parfait]], il existe une infinité de nombres premiers modulo lesquels {{mvar|n}} n'est pas un résidu quadratique<ref>Pour une preuve ''sans'' le théorème de la progression arithmétique, voir (pour ''n'' ∈ ℕ) {{Harvsp|Ireland|Rosen|1990|p=57-58}} (chap. 5, § 2, th. 3) ou {{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Devoir/Principe local-global pour les carrés|ce ''devoir'' corrigé de la leçon « Introduction à la théorie des nombres »|début=(pour ''n'' ∈ ℤ)}}</ref>{{,}}<ref>Sur des problèmes connexes, voir « [[Théorème de Grunwald-Wang]] » et {{Lien web|lang=en|url=https://mathoverflow.net/questions/135820|titre=Does there exist a non-square number which is the quadratic residue of every prime?|site=[[MathOverflow]]}}.</ref>, et que pour tout ensemble fini <math>S\subset\Z</math>, il existe une infinité<ref>Plus précisément, la [[densité asymptotique]] relative ''D'' (dans l'ensemble des nombres premiers) de l'ensemble infini des solutions <math>p</math> est non nulle et s'exprime simplement : on se ramène facilement (en ôtant de ''S'' les éléments redondants) au cas où aucun produit d'éléments de ''S'' n'est un [[Carré parfait|carré]] à part le [[produit vide]], et l'on démontre qu'alors, ''D'' =  2{{exp|–{{!}}S{{!}}}}, à l'aide de la [[Théorème de la progression arithmétique#Version quantitative|version quantitative du théorème de la progression arithmétique]] : voir {{Harvsp|Wright|2016}} (th. 4.9) ou {{Article |lang=en |auteur=[[Ramachandran Balasubramanian|R. Balasubramanian]] |auteur2=F. Luca |auteur3=R. Thangadurai |titre=On the exact degree of <math>\Q(\sqrt{a_1}, \sqrt{a_2},\ldots,\sqrt{a_\ell})</math> over <math>\Q</math> |revue=[[Proceedings of the American Mathematical Society|Proc. Amer. Math. Soc.]] |vol=138 |année=2010 |doi=10.1090/S0002-9939-10-10331-1 |p.=2283-2288 }}, ou encore la preuve (bien plus simple) de l'''exercice'' corrigé sur [[Wikiversité]] déjà signalé.</ref> de nombres premiers <math>p</math> tels que chaque élément de <math>S</math> est un carré <math>\bmod p</math>.

== Modulo une [[Nombre primaire|puissance d'un nombre premier]] ==
Modulo 2{{exp|''r''}} avec ''r'' ≥ 3, les résidus quadratiques sont<ref>{{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Résidus quadratiques#Exercice 4-10|cet exercice corrigé|début=Voir}}</ref> 0 et les entiers de la forme 4{{exp|''k''}}(8''m'' + 1).

Pour ''p'' premier impair, tout entier non divisible par ''p'' qui est un carré mod ''p'' est aussi un carré mod ''p{{exp|r}}'' — en effet<ref>{{Note autre projet|Wikiversité|Introduction à la théorie des nombres/Exercices/Résidus quadratiques#Exercice 4-9|cet exercice corrigé|début=Voir aussi}}</ref>, 
si α est une [[racine primitive modulo n|racine primitive modulo ''p{{exp|r}}'']], c'est une racine primitive modulo ''p''. Donc si un élément α{{exp|k}} du [[Anneau Z/nZ#Cas où n n'est pas premier|groupe des unités (ℤ/''p{{r}}''ℤ){{exp|×}} de ℤ/''p{{r}}''ℤ]] est un carré modulo ''p'', son exposant ''k'' est pair, et est donc un carré modulo ''p{{exp|r}}'' — et les résidus quadratiques mod ''p{{exp|r}}'' sont les ''p{{exp|k}}n'' avec ''k'' ≥ ''r'', ou [[Symbole de Legendre|(''n''/''p'')]] = 1 et ''k'' pair < ''r''.

== Localisation ==
Soit {{mvar|p}} un nombre premier impair. Le plus petit entier {{mvar|n}} qui n'est pas un résidu quadratique modulo {{mvar|p}} vérifie <math>n < 1 + \sqrt p</math><ref name=boyer/> et même, si <math>p\not\equiv1\pmod8</math>, <math>n < p^{\frac25} + 12p^{\frac15}+33</math><ref name=boyer/>.

Plus généralement, on [[conjecture]]<ref name=boyer/> que pour tout <math>\varepsilon > 0</math>, pour tout nombre premier {{mvar|p}} assez grand, cet entier {{mvar|n}} est inférieur à <math>p^\varepsilon</math>.

== Notes et références ==
{{Traduction/Référence|en|Quadratic residue|7042082|type=note}}
{{Références}}

== Voir aussi ==
{{Autres projets|v=Introduction à la théorie des nombres/Résidus quadratiques}}
=== Articles connexes ===
*[[Problème de la résiduosité quadratique]]
*[[Lemme de Hensel]]
=== Liens externes ===
*{{MathWorld|nom_url=QuadraticResidue|titre=Quadratic Residue}}
*{{Article|lang=en|prénom=Walter D.|nom=Stangl|titre=Counting Squares in ℤ{{ind|''n''}}|lien périodique=Mathematics Magazine|revue=Math. Mag.|vol=69|numéro=4|année=1996|p.=285-289|url=http://www.maa.org/programs/faculty-and-departments/classroom-capsules-and-notes/counting-squares-in-zn}}
*{{Ouvrage|prénom1=C. F.|nom1=Gauss|lien auteur1=Carl Friedrich Gauss|titre=[[Recherches arithmétiques]]|lire en ligne=https://archive.org/stream/recherchesarithm00gaus#page/74/mode/2up}}, § 101 et 102

{{portail|arithmétique}}

[[Catégorie:Arithmétique modulaire]]