Quadratic Residue (redirected from Square root mod n)

quadratic residue [kwä¦drad·ik ′rez·ə·dü]

(mathematics)

A residue of order 2.

---

Quadratic Residue 

a concept in number theory. A number a for which the congruence x² ≡ a (mod m ) has a solution is called a quadratic residue modulo m; in other words, a is a quadratic residue modulo m if for a certain integer x the number x² − a is divisible by m; if this congruence has no solution, then a is called a quadratic nonresidue. For example, if m = 11, then the number 3 is a quadratic residue, since the congruence x² ≡ 3 (mod 11) has the solutions x − 5 and x = 6, and the number 2 is a nonresidue, since there do not exist any numbers x that satisfy the congruence x² ≡ 2 (mod 11). Quadratic residues are a particular case of residues of degree n for n = 2. If m is equal to an odd prime p, then among the numbers 1, 2, …, p − 1 there are (p − l)/2 quadratic residues and p − l)/2 quadratic nonresidues. The Legendre symbol (a/p) is introduced in order to study quadratic residues for a prime modulus p. It is defined as follows: if a is relatively prime to p, then we put (a/p ) = 1 when a is a quadratic residue and (a/p) = − 1 when a is a quadratic nonresidue. A fundamental theorem is the law of quadratic reciprocity, which states that if p and q are odd primes, then

This relation was discovered about 1772 by L. Euler, a modern formulation was given by A. Legendre, and a complete proof was first given in 1801 by K. Gauss. A convenient generalization of the Legendre symbol is the Jacobi symbol. There are many generalizations of the law of quadratic reciprocity in the theory of algebraic numbers. The distribution of quadratic residues and of the sums of the values of the Legendre symbol has been studied by I. M. Vinogradov and other mathematicians.

REFERENCE

Vinogradov, I. M. Osnovy teorii chisel Moscow, 1972.