quadratic residue

In the study of diophantine equations (and surprisingly often in the study of primes) it is important to know whether the integer a is the square of an integer modulo p. If it is, we say a is a quadratic residue modulo p; otherwise, it is a quadratic non-residue modulo p. For example, 42=7 (mod 9) so 7 is a quadratic residue modulo 9. Lets look at a few more examples:

modulusquadratic
residues
quadratic
non-residues
20,1(none)
30,12
40,12,3
50,1,42,3
6 0,1,3,42,5
7 0,1,2,43,5,6
8 0,1,42,3,5,6,7

For an odd prime p, there are (p+1)/2 quadratic residues (counting zero) and (p-1)/2 non-residues. (The residues come from the numbers 02, 12, 22, ... , {(p-1)/2}2, these are all different modulo p and clearly list all possible squares modulo p.)

When the base is a product of odd prime powers, and the numbers in question are relatively prime to the base, then

One of the most important results about quadratic residues is expressed in the surprisingly difficult to prove quadratic reciprocity theorem (see the entry on the Legendre symbol).

See Also: LegendreSymbol, JacobiSymbol

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.