Résidu quadratique

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En arithmétique modulaire, on dit qu'un entier naturel q est un résidu quadratique modulo p s'il existe un entier x tel que :

(dans le cas contraire, on dit que q est un non-résidu quadratique modulo p).

Autrement dit, un résidu quadratique modulo p est un nombre qui possède une racine carrée en arithmétique modulaire de module p.

Selon cette définition, par exemple :

  • modulo 4, les résidus quadratiques sont les entiers congrus à 22 ≡ 02 = 0 ou à (±1)2 = 1 donc les non-résidus quadratiques sont 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[1],[2] excluent ces deux derniers cas de la définition et imposent même que p et q soient premiers entre eux.

Modulo un entier quelconque[modifier | modifier le code]

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 (c.-à-d. si est pair et si est impair).

On peut même se limiter à , puisque .

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 à .

Soient a et b deux entiers premiers entre eux. Un entier x est un résidu quadratique mod ab si (et bien sûr seulement si) est un résidu quadratique à la fois mod a et mod b.

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[modifier | modifier le code]

Soit p un nombre premier impair. Pour tout entier n, le symbole de Legendre (n/p) vaut, par définition :

D'après le critère d'Euler, il est congru modulo p à n(p–1)/2. 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 n est un résidu quadratique modulo p. Le théorème de la progression arithmétique permet[3] d'en déduire que si n n'est pas un carré parfait, il existe une infinité de nombres premiers modulo lesquels n n'est pas un résidu quadratique[4],[5], et que pour tout ensemble fini , il existe une infinité[6] de nombres premiers tels que chaque élément de est un carré .

Modulo une puissance d'un nombre premier[modifier | modifier le code]

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

Pour p premier impair, tout entier non divisible par p qui est un carré mod p est aussi un carré mod pr — en effet, le groupe des unités (ℤ/prℤ)× de ℤ/pr est cyclique, engendré par [α(1 + p) mod pr] où [α mod p] est un générateur de (ℤ/pℤ)×, or si [(α(1 + p))s mod p] = [αs mod p] est un carré alors s est pair — et les résidus quadratiques mod pr sont les pkn avec kr, ou (n/p) = 1 et k pair < r.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Quadratic residue » (voir la liste des auteurs).
  1. Gauss, § 96 et 105.
  2. (en) Kenneth Ireland et Michael Rosen, A Classical Introduction to Modern Number Theory, Springer, coll. « GTM » (no 84), (lire en ligne), p. 50.
  3. (en) Steve Wright, Quadratic Residues and Non-Residues: Selected Topics, Springer, coll. « Lecture Notes in Mathematics » (no 2171), (arXiv 1408.0235, lire en ligne), théorèmes 4.2 et 4.3, et « Patterns of quadratic residues and nonresidues for infinitely many primes », J. Number Theory, vol. 123, no 1,‎ , 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 cet exercice corrigé de la leçon « Introduction à la théorie des nombres » sur la Wikiversité.
  4. Pour une preuve sans le théorème de la progression arithmétique, voir (pour n ∈ ℕ) Ireland et Rosen 1990, p. 57-58 (chap. 5, § 2, th. 3) ou (pour n ∈ ℤ) ce devoir corrigé de la leçon « Introduction à la théorie des nombres » sur la Wikiversité.
  5. Sur des problèmes connexes, voir « Théorème de Grunwald-Wang » et (en) « Does there exist a non-square number which is the quadratic residue of every prime? », sur MathOverflow.
  6. 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–|S|, à l'aide de la version quantitative du théorème de la progression arithmétique : voir Wright 2016 (th. 4.9) ou (en) R. Balasubramanian (en), F. Luca et R. Thangadurai, « On the exact degree of over  », Proc. Amer. Math. Soc., vol. 138,‎ , p. 2283-2288 (DOI 10.1090/S0002-9939-10-10331-1), ou encore la preuve (bien plus simple) de l'exercice corrigé sur Wikiversité déjà signalé.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]