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, 4²=7 (mod 9) so 7 is a quadratic residue modulo 9. Lets look at a few more examples:

modulus	quadratic residues	quadratic non-residues
2	0,1	(none)
3	0,1	2
4	0,1	2,3
5	0,1,4	2,3
6	0,1,3,4	2,5
7	0,1,2,4	3,5,6
8	0,1,4	2,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 0², 1², 2², ... , {(p-1)/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