In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract mathematical concept from the branch of number theory known as modular arithmetic, quadratic residues are now used in applications ranging from acoustical engineering to cryptography and the factoring of large numbers. Fermat, Euler, Lagrange, Legendre, and other number theorists of the 17th and 18th centuries established theorems and formed conjectures about quadratic residues, but the first systematic treatment is § IV of Gauss's Disquisitiones Arithmeticae (1801). Article 95 introduces the terminology "quadratic residue" and "quadratic nonresidue", and states that if the context makes it clear, the adjective "quadratic" may be dropped. For a given n a list of the quadratic residues modulo n may be obtained by simply squaring the numbers 0, 1, ..., n − 1. Because a2 ≡ (n − a)2 (mod n), the list of squares modulo n is symmetric around n/2, and the list only needs to go that high. This can be seen in the table below. Thus, the number of quadratic residues modulo n cannot exceed n/2 + 1 (n even) or (n + 1)/2 (n odd). The product of two residues is always a residue. Modulo 2, every integer is a quadratic residue. Modulo an odd prime number p there are (p + 1)/2 residues (including 0) and (p − 1)/2 nonresidues, by Euler's criterion. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the field Z/pZ. (In other words, every congruence class except zero modulo p has a multiplicative inverse. This is not true for composite moduli.) Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue. Following this convention, modulo an odd prime number there are an equal number of residues and nonresidues.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications (60)
Related concepts (18)
Euler's criterion
In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely, Let p be an odd prime and a be an integer coprime to p. Then Euler's criterion can be concisely reformulated using the Legendre symbol: The criterion first appeared in a 1748 paper by Leonhard Euler. The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details.
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.
Jacobi symbol
Jacobi symbol k/n for various k (along top) and n (along left side). Only 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. Quadratic residues are highlighted in yellow — note that no entry with a Jacobi symbol of −1 is a quadratic residue, and if k is a quadratic residue modulo a coprime n, then k/n = 1, but not all entries with a Jacobi symbol of 1 (see the n = 9 and n = 15 rows) are quadratic residues. Notice also that when either n or k is a square, all values are nonnegative.
Show more
Related MOOCs (9)
Algebra (part 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algebra (part 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algebra (part 2)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Show more

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.