The Legendre symbol is a notation used for stating a central theorem of elementary number theory, the quadratic reciprocity law. This theorem was first proved by Carl Friedrich Gauss in 1801, after the French mathematician Adrien-Marie Legendre had published two incorrect proofs. As a sort of consolation prize, tradition has named the notation after Legendre.

The quadratic reciprocity law gives an effective procedure for determining whether a number is a perfect square in modular arithmetic. For example, 2 is a square modulo 7, because it is congruent to the number 9 = 3^^*2. By contrast, 3 is not a square modulo 7. It is congruent to the numbers 10, 17, 24, 31,..., none of which is the square of a whole number.

In the real number system, it is easy to tell squares and non-squares apart. Squares are positive or zero, and non-squares are negative. But it is much less obvious how to tell whether a number x...