quadratic residue
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: 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

  • the product of two residues, or two non-residues, is a residue
  • the product of a residue that is not a zero-divisor and a non-residue is a non-residue.
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


Chris K. Caldwell © 1999-2017 (all rights reserved)