Résidu quadratique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 :

{x^2}\equiv{q} \pmod{p}.

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

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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[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).