Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Résidu quadratique
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.