En mathématiques, plus précisément en arithmétique modulaire, un entier naturel est un résidu quadratique modulo s'il possède une racine carrée en arithmétique modulaire de module . Autrement dit, est un résidu quadratique modulo s'il existe un entier tel que :
.
Dans le cas contraire, on dit que est un non-résidu quadratique modulo
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 , tout multiple de est un résidu quadratique. Pour cette raison, certains auteurs.. excluent les multiples de de la définition et imposent même que et soient premiers entre eux.
Modulo un entier quelconque Modulo un entier , la classe de ne dépend que de celle de , donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de par en faisant varier dans , ou dans n'importe quel ensemble de entiers consécutifs, comme ( si est pair et si est impair).
On peut même se limiter à , puisque .
En outre, 0 et 1 sont toujours résidus quadratiques.
Soient et deux entiers premiers entre eux. Un entier est un résidu quadratique si (et bien sûr seulement si) est un résidu quadratique à la fois et .
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 un nombre premier impair. Pour tout entier , le symbole de Legendre vaut, par définition :
D'après le critère d'Euler, il est congru modulo à . 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 est un résidu quadratique modulo p. Le théorème de la progression arithmétique permet, théorèmes 4.2 et 4.3, et . Pour une généralisation simultanée de ces deux théorèmes, voir . d'en déduire que si n'est pas un carré parfait, il existe une infinité de nombres premiers modulo lesquels n'est pas un résidu quadratiquePour une preuve sans le théorème de la progression arithmétique, voir (pour n ∈ ℕ) (chap. 5, § 2, th. 3) ou Sur des problèmes connexes, voir « Théorème de Grunwald-Wang » et ., et que pour tout ensemble fini , il existe une infinitéPlus précisément, la densité asymptotique relative D (dans l'ensemble des nombres premiers) de l'ensemble infini des solutions 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, à l'aide de la version quantitative du théorème de la progression arithmétique : voir (th. 4.9) ou , ou encore la preuve (bien plus simple) de l'exercice corrigé sur Wikiversité déjà signalé. de nombres premiers tels que chaque élément de est un carré .
Modulo une puissance d'un nombre premier Modulo 2 avec r ≥ 3, les résidus quadratiques sont 0 et les entiers de la forme 4(8m + 1).
Pour p premier impair, tout entier non divisible par p qui est un carré mod p est aussi un carré mod p — en effet, si α est une racine primitive modulo p, c'est une racine primitive modulo p. Donc si un élément α du groupe des unités (ℤ/pℤ) de ℤ/pℤ est un carré modulo p, son exposant k est pair, et est donc un carré modulo p — et les résidus quadratiques mod p sont les pn avec k ≥ r, ou (n/p) = 1 et k pair < r.
Localisation Soit un nombre premier impair. Le plus petit entier qui n'est pas un résidu quadratique modulo vérifie et même, si , .
Plus généralement, on conjecture que pour tout , pour tout nombre premier assez grand, cet entier est inférieur à .
Notes et références
Voir aussi
Articles connexes Problème de la résiduosité quadratique Lemme de Hensel Liens externes
, § 101 et 102
Catégorie:Arithmétique modulaire