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.

À 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.
Cours associés (25)
COM-401: Cryptography and security
This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how
MATH-207(d): Analysis IV
The course studies the fundamental concepts of complex analysis and Laplace analysis with a view to their use to solve multidisciplinary scientific engineering problems.
MATH-351: Advanced numerical analysis II
The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.
Afficher plus
Concepts associés (18)
Critère d'Euler
En mathématiques et plus précisément en arithmétique modulaire, le critère d'Euler est un théorème utilisé en théorie des nombres pour déterminer si un entier donné est un résidu quadratique (autrement dit, un carré) modulo un nombre premier. Soient un nombre premier différent de 2 et un entier premier avec . Si est un résidu quadratique modulo , alors . Si n'est pas un résidu quadratique modulo alors . Ce qui se résume, en utilisant le symbole de Legendre, par : La preuve repose sur le petit théorème de Fermat et sur le fait que dans un anneau intègre, un polynôme n'a jamais plus de racines que son degré.
Quartic reciprocity
Quartic or biquadratic reciprocity is a collection of theorems in elementary and algebraic number theory that state conditions under which the congruence x4 ≡ p (mod q) is solvable; the word "reciprocity" comes from the form of some of these theorems, in that they relate the solvability of the congruence x4 ≡ p (mod q) to that of x4 ≡ q (mod p). Euler made the first conjectures about biquadratic reciprocity. Gauss published two monographs on biquadratic reciprocity.
Symbole de Jacobi
vignette|Charles Jacobi, mathématicien à l'origine du symbole de Jacobi Le symbole de Jacobi est utilisé en mathématiques dans le domaine de la théorie des nombres. Il est nommé ainsi en l'honneur du mathématicien prussien Charles Gustave Jacob Jacobi. C'est une généralisation du symbole de Legendre. Le symbole de Jacobi est défini pour tout entier relatif et tout entier naturel impair comme produit de symboles de Legendre, en faisant intervenir la décomposition en facteurs premiers de : pour tout et tous nombres premiers impairs (non nécessairement distincts), Soient positifs impairs et entiers quelconques.
Afficher plus
MOOCs associés (9)
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 2)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Afficher plus

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.