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 : 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 à 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 excluent les multiples de p de la définition et imposent même que p et q soient premiers entre eux. 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 , ou dans n'importe quel ensemble de n entiers consécutifs, comme ( 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. 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. 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.