Quadratic Residue


Also found in: Acronyms, Wikipedia.

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 x2a (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 x2a 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 x2 ≡ 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 x2 ≡ 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.
References in periodicals archive ?
Let * = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the quadratic residue character, which is 1 on the quadratic residues Q [subset] GF[(p).
We call this a long quadratic residue code, or LQR code for short, and identify it with a subset of [F.
Voloch, Double circulant quadratic residue codes, IEEE Transactions in Information Theory, Volume 50, Issue 9, Sept.
Voloch, Asymptotics of the minimal distance of quadratic residue codes, preprint.
Q](GF(p))j = 1:5p + a, where Q is the set of quadratic residues and a is a small constant, -1/2 [less than or equal to] a [less than or equal to] 5/2.
p], the set of quadratic residues modulo p, and secondly use all these results to determine the above number.
By [4], we know that the number of pairs of consecutive quadratic residues modulo p is given by the formula
p] = p - 3/4 is the number of quadratic residues at each column and hence we obtain the following result.
As every column (and row) has the same number of quadratic residues (and non-residues), we can consider the column consisting of the entries x + 1 (taking y = 1 [member of] [Q.

Full browser ?