Aller au contenu

Résidu quadratique

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, plus précisément en arithmétique modulaire, un entier naturel q est un résidu quadratique modulo n s'il possède une racine carrée en arithmétique modulaire de module n. Autrement dit, q est un résidu quadratique modulo n s'il existe un entier x tel que :

.

Dans le cas contraire, on dit que q est un non-résidu quadratique modulo n

Par exemple :

  • modulo 4, les résidus quadratiques sont les entiers congrus à 22 ≡ 02 = 0 ou à (±1)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 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 quelconque

[modifier | modifier le code]

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.

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 2r avec r ≥ 3, les résidus quadratiques sont[8] 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[9], si α est une racine primitive modulo pr, c'est une racine primitive modulo p. Donc si un élément αk du groupe des unités (ℤ/prℤ)× de ℤ/pr est un carré modulo p, son exposant k est pair, et est donc un carré modulo pr — et les résidus quadratiques mod pr sont les pkn avec kr, ou (n/p) = 1 et k pair < r.

Localisation

[modifier | modifier le code]

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é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 Wikiversité.
  4. a b c et d Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, 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, 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é.
  8. Voir cet exercice corrigé sur Wikiversité.
  9. Voir aussi cet exercice corrigé sur Wikiversité.

Sur les autres projets Wikimedia :

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]