Résidu quadratique

En mathématiques, plus précisément en arithmétique modulaire, un entier naturel q est un résidu quadratique modulo p s'il possède une racine carrée en arithmétique modulaire de module p. Autrement dit, 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

ExemplesModifier

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 les multiples de p de la définition et imposent même que p et q soient premiers entre eux.

Modulo un entier quelconqueModifier

Modulo un entier n > 0, la classe de x2 ne dépend que de celle de x, donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de x2 par n en faisant varier x dans  , ou dans n'importe quel ensemble de n entiers consécutifs, comme   (c.-à-d.   si n est pair et   si n 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 impairModifier

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],[4] 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[5],[6], et que pour tout ensemble fini  , il existe une infinité[7] de nombres premiers   tels que chaque élément de   est un carré  .

Modulo une puissance d'un nombre premierModifier

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.

LocalisationModifier

Soit p un nombre premier impair. Le plus petit entier n qui n'est pas un résidu quadratique modulo p vérifie  [4] et même, si  ,  [4].

Plus généralement, on conjecture[4] que pour tout  , pour tout nombre premier p assez grand, cet entier n est inférieur à  .

Notes et référencesModifier

(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 Wikiversité.
  4. a b c et d Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, , 648 p. (ISBN 978-2-916352-75-6), Arithmétique de ℤ, chap. I.3.2 (« Résidus quadratiques : applications »), p. 47-49.
  5. 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 Wikiversité.
  6. 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.
  7. 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 aussiModifier

Articles connexesModifier

Liens externesModifier