# Résidu quadratique

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$^2$ ≡ 0$^2$ = 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$^,$ 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$^2$ ne dépend que de celle de x, donc les résidus quadratiques sont les restes obtenus dans la division euclidienne de x$^2$ 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.
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.
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$^,$ 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 ensemble fini $S\subset \mathbb {Z}$, il existe une infinité 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 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, 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$^k$n 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}}$ et même, si $p\not \equiv 1{\pmod {8}}$, $n<p^{\frac {2}{5}}+12p^{\frac {1}{5}}+33$.
Plus généralement, on conjecture que pour tout $\varepsilon >0$, pour tout nombre premier p assez grand, cet entier n est inférieur à $p^{\varepsilon }$.