Résidu quadratique

{{#invoke:Bandeau|ébauche}} En mathématiques, plus précisément en arithmétique modulaire, un entier naturel Modèle:Mvar est un résidu quadratique modulo Modèle:Mvar s'il possède une racine carrée en arithmétique modulaire de module Modèle:Mvar. Autrement dit, Modèle:Mvar est un résidu quadratique modulo Modèle:Mvar s'il existe un entier Modèle:Mvar tel que :

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

Dans le cas contraire, on dit que Modèle:Mvar est un non-résidu quadratique modulo Modèle:Mvar

Exemples

Par exemple :

• modulo 4, les résidus quadratiques sont les entiers congrus à 2² ≡ 0² = 0 ou à (±1)² = 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>Modèle:Harvsp.</ref><ref>Modèle:Ouvrage.</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 Modèle:Math, la classe de Modèle:Mvar² ne dépend que de celle de Modèle:Mvar, donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de Modèle:Mvar² par Modèle:Mvar en faisant varier Modèle:Mvar dans <math>\left\{0,1,\dots,n-1\right\}</math>, ou dans n'importe quel ensemble de Modèle:Mvar 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> (Modèle:C.-à-d. <math>\left\{-\frac n2+1,\dots,\frac n2\right\}</math> si Modèle:Mvar est pair et <math>\left\{-\frac{n-1}2,\dots,\frac{n-1}2\right\}</math> si Modèle:Mvar 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.

Modèle:Exemple Soient Modèle:Mvar et Modèle:Mvar deux entiers premiers entre eux. Un entier Modèle:Mvar est un résidu quadratique Modèle:Math si (et bien sûr seulement si) <math>x</math> est un résidu quadratique à la fois Modèle:Math et Modèle:Math.

Cette propriété permet de ramener la détermination des résidus quadratiques modulo un entier quelconque à celle des résidus modulo les puissances de nombres premiers qui apparaissent dans sa décomposition.

Modulo un nombre premier impair

Soit Modèle:Mvar un nombre premier impair. Pour tout entier Modèle:Mvar, le symbole de Legendre Modèle:Math 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 Modèle:Mvar à Modèle:Math. Le 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 4n, qui détermine si Modèle:Mvar est un résidu quadratique modulo p. Le théorème de la progression arithmétique permet<ref>Modèle:Ouvrage, théorèmes 4.2 et 4.3, et Modèle:Article. Pour une généralisation simultanée de ces deux théorèmes, voir Modèle:Note autre projet</ref><ref name=boyer>Modèle:Ouvrage.</ref> d'en déduire que si Modèle:Mvar n'est pas un carré parfait, il existe une infinité de nombres premiers modulo lesquels Modèle:Mvar n'est pas un résidu quadratique<ref>Pour une preuve sans le théorème de la progression arithmétique, voir (pour n ∈ ℕ) Modèle:Harvsp (chap. 5, § 2, th. 3) ou Modèle:Note autre projet</ref><ref>Sur des problèmes connexes, voir « Théorème de Grunwald-Wang » et Modèle:Lien web.</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é à part le produit vide, et l'on démontre qu'alors, D = 2^–|S|, à l'aide de la version quantitative du théorème de la progression arithmétique : voir Modèle:Harvsp (th. 4.9) ou Modèle:Article, 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 puissance d'un nombre premier

Modulo 2^r avec r ≥ 3, les résidus quadratiques sont<ref>Modèle:Note autre projet</ref> 0 et les entiers de la forme 4^k(8m + 1).

Pour p premier impair, tout entier non divisible par p qui est un carré mod p est aussi un carré mod p^r — en effet<ref>Modèle:Note autre projet</ref>, si α est une racine primitive modulo p^r, c'est une racine primitive modulo p. Donc si un élément α^k du groupe des unités (ℤ/p^rℤ)^× de ℤ/p^rℤ est un carré modulo p, son exposant k est pair, et est donc un carré modulo p^r — et les résidus quadratiques mod p^r sont les p^kn avec k ≥ r, ou (n/p) = 1 et k pair < r.

Localisation

Soit Modèle:Mvar un nombre premier impair. Le plus petit entier Modèle:Mvar qui n'est pas un résidu quadratique modulo Modèle:Mvar 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 Modèle:Mvar assez grand, cet entier Modèle:Mvar est inférieur à <math>p^\varepsilon</math>.

Voir aussi

Articles connexes

• Problème de la résiduosité quadratique
• Lemme de Hensel

Liens externes

• Modèle:MathWorld
• Modèle:Article
• Modèle:Ouvrage, § 101 et 102