# 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^{2}=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^{2}, 1^{2}, 2^{2}, ... ,
{(*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