Résidu quadratique

Modèle:É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 :

$x^2\equiv q(\mathrm{mod}n)$.

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 à 2Modèle:2 ≡ 0Modèle:2 = 0 ou à (±1)Modèle: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 auteursModèle:, 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:MvarModèle:2 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:MvarModèle:2 par Modèle:Mvar en faisant varier Modèle:Mvar dans $\{0,1,\dots ,n-1\}$, ou dans n'importe quel ensemble de Modèle:Mvar entiers consécutifs, comme $\{\lfloor \frac{-n}{2}\rfloor +1,\lfloor \frac{-n}{2}\rfloor +2,\dots ,\lfloor \frac{n}{2}\rfloor \}$ (Modèle:C.-à-d. $\{-\frac{n}{2}+1,\dots ,\frac{n}{2}\}$ si Modèle:Mvar est pair et $\{-\frac{n-1}{2},\dots ,\frac{n-1}{2}\}$ si Modèle:Mvar est impair).

On peut même se limiter à $x\in \{0,1,...,\lfloor \frac{n}{2}\rfloor \}$, puisque ${(-x)}^2=x^2$.

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) $x$ 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 :

$\left(\frac{n}{p}\right)=\{\begin{array}{cc}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{array}$

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 permetModèle:, 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 quadratiqueModèle:,, et que pour tout ensemble fini $S\subset \mathbb{Z}$, il existe une infinité de nombres premiers $p$ tels que chaque élément de $S$ est un carré $modp$.

Modulo une puissance d'un nombre premier

Modulo 2Modèle:Exp avec r ≥ 3, les résidus quadratiques sont 0 et les entiers de la forme 4Modèle:Exp(8m + 1).

Pour p premier impair, tout entier non divisible par p qui est un carré mod p est aussi un carré mod pModèle:Exp — en effet, si α est une [[racine primitive modulo n|racine primitive modulo pModèle:Exp]], c'est une racine primitive modulo p. Donc si un élément αModèle:Exp du [[Anneau Z/nZ#Cas où n n'est pas premier|groupe des unités (ℤ/pModèle:Rℤ)Modèle:Exp de ℤ/pModèle:Rℤ]] est un carré modulo p, son exposant k est pair, et est donc un carré modulo pModèle:Exp — et les résidus quadratiques mod pModèle:Exp sont les pModèle:Expn 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 $n<1+\sqrt{p}$ et même, si $p\equiv ̸1(\mathrm{mod}8)$, $n<p^{\frac{2}{5}}+12p^{\frac{1}{5}}+33$.

Plus généralement, on conjecture que pour tout $\epsilon >0$, pour tout nombre premier Modèle:Mvar assez grand, cet entier Modèle:Mvar est inférieur à $p^{\epsilon }$.

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