Résidu quadratique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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 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, 0 si n est divisible par p, 1 sinon et si n est un résidu quadratique modulo p, et –1 sinon. 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 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, et que pour tout n, il existe une infinité de nombres premiers modulo lesquels 1, 2, … , n sont tous des résidus quadratiques.

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.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]