Résidu quadratique

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

{x^{2}}\equiv q{\pmod {n}}

.

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

Exemples

Par exemple :

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

Modulo un entier $n > 0$ , la classe de $x$ ² ne dépend que de celle de $x$ , donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de $x$ ² par $n$ en faisant varier $x$ dans $\left\{0,1,\dots ,n-1\right\}$ , ou dans n'importe quel ensemble de $n$ entiers consécutifs, comme $\left\{\left\lfloor {\frac {-n}{2}}\right\rfloor +1,\left\lfloor {\frac {-n}{2}}\right\rfloor +2,\dots ,\left\lfloor {\frac {n}{2}}\right\rfloor \right\}$ (c.-à-d. $\left\{-{\frac {n}{2}}+1,\dots ,{\frac {n}{2}}\right\}$ si $n$ est pair et $\left\{-{\frac {n-1}{2}},\dots ,{\frac {n-1}{2}}\right\}$ si $n$ est impair).

On peut même se limiter à $x\in \left\{0,1,...,\left\lfloor {\frac {n}{2}}\right\rfloor \right\}$ , puisque $\left(-x\right)^{2}=x^{2}$ .

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 à $x\in \{0,1,...,5\}$ .

{\begin{array}{|c|c|c|c||c|c|c|}x&-4&-3&-2&-1&0&1&2&3&4&5\\\hline x^{2}&{\color {magenta}6}&{\color {cyan}9}&{\color {blue}4}&{\color {green}1}&{\color {red}0}&{\color {green}1}&{\color {blue}4}&{\color {cyan}9}&{\color {magenta}6}&{\color {brown}5}\end{array}}

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) $x$ est un résidu quadratique à la fois $mod a$ et $mod b$ .

Démonstration

Si $x\equiv u^{2}{\bmod {a}}$ et $x\equiv v^{2}{\bmod {b}}$ , soit (par le théorème des restes chinois) un entier $w$ tel que $w\equiv u{\bmod {a}}$ et $w\equiv v{\bmod {b}}$ . Alors, $x\equiv w^{2}{\bmod {a}}$ et $x\equiv w^{2}{\bmod {b}}$ donc (par le lemme de Gauss) $x\equiv w^{2}{\bmod {ab}}$ .

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

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

\left({\frac {n}{p}}\right)={\begin{cases}\;\;\,0&{\text{ si }}n{\text{ est divisible par }}p\\+1&{\text{ si }}n{\text{ n'est pas divisible par }}p{\text{ et est un résidu quadratique modulo }}p\\-1&{\text{ si }}n{\text{ n'est pas un résidu quadratique modulo }}p.\end{cases}}

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 $S\subset \mathbb {Z}$ , il existe une infinité^[7] de nombres premiers $p$ tels que chaque élément de $S$ est un carré ${\bmod {p}}$ .

Modulo une puissance d'un nombre premier

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

Pour p premier impair, tout entier non divisible par p qui est un carré mod p est aussi un carré mod p^r — en effet^[9], si α est une racine primitive modulo p^r, c'est une racine primitive modulo p. Donc si un élément α^k du groupe des unités (ℤ/p^rℤ)^× de ℤ/p^rℤ est un carré modulo p, son exposant k est pair, et est donc un carré modulo p^r — et les résidus quadratiques mod p^r sont les p^kn avec k ≥ r, ou (n/p) = 1 et k pair < r.

Localisation

Soit $p$ un nombre premier impair. Le plus petit entier $n$ qui n'est pas un résidu quadratique modulo $p$ vérifie $n<1+{\sqrt {p}}$ ^[4] et même, si $p\not \equiv 1{\pmod {8}}$ , $n<p^{\frac {2}{5}}+12p^{\frac {1}{5}}+33$ ^[4].

Plus généralement, on conjecture^[4] que pour tout $\varepsilon >0$ , pour tout nombre premier $p$ assez grand, cet entier $n$ est inférieur à $p^{\varepsilon }$ .

Notes et références

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

↑ Gauss, § 96 et 105.
↑ (en) Kenneth Ireland et Michael Rosen, A Classical Introduction to Modern Number Theory, Springer, coll. « GTM » (n^o 84), 1990 (lire en ligne), p. 50.
↑ (en) Steve Wright, Quadratic Residues and Non-Residues : Selected Topics, Springer, coll. « Lecture Notes in Mathematics » (n^o 2171), 2016 (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, n^o 1,‎ 2007, 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é.
↑ ^{a b c et d} Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), Arithmétique de ℤ, chap. I.3.2 (« Résidus quadratiques : applications »), p. 47-49.
↑ 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é.
↑ 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.
↑ Plus précisément, la densité asymptotique relative D (dans l'ensemble des nombres premiers) de l'ensemble infini des solutions $p$ 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 $\mathbb {Q} ({\sqrt {a_{1}}},{\sqrt {a_{2}}},\ldots ,{\sqrt {a_{\ell }}})$ over $\mathbb {Q}$ », Proc. Amer. Math. Soc., vol. 138,‎ 2010, 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 cet exercice corrigé sur Wikiversité.
↑ Voir aussi cet exercice corrigé sur Wikiversité.

Voir aussi

Sur les autres projets Wikimedia :

Résidu quadratique, sur Wikiversity

Articles connexes

Liens externes

(en) Eric W. Weisstein, « Quadratic Residue », sur MathWorld
(en) Walter D. Stangl, « Counting Squares in ℤ_n », Math. Mag., vol. 69, n^o 4,‎ 1996, p. 285-289 (lire en ligne)
C. F. Gauss, Recherches arithmétiques (lire en ligne), § 101 et 102

Arithmétique et théorie des nombres

[1] Gauss, § 96 et 105.

[2] (en) Kenneth Ireland et Michael Rosen, A Classical Introduction to Modern Number Theory, Springer, coll. « GTM » (n^o 84), 1990 (lire en ligne), p. 50.

[3] (en) Steve Wright, Quadratic Residues and Non-Residues : Selected Topics, Springer, coll. « Lecture Notes in Mathematics » (n^o 2171), 2016 (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, n^o 1,‎ 2007, 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é.

[boyer-4] {a b c et d} Pascal Boyer, Petit compagnon des nombres et de leurs applications, Paris, Calvage et Mounet, 2019, 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 $p$ 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 $\mathbb {Q} ({\sqrt {a_{1}}},{\sqrt {a_{2}}},\ldots ,{\sqrt {a_{\ell }}})$ over $\mathbb {Q}$ », Proc. Amer. Math. Soc., vol. 138,‎ 2010, 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é.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]