Quadratic reciprocity is the relation between the solvability of the congruences
and
for distinct odd primes
and
. In terms of Legendre
symbols, the relation is
Thus
is a quadratic residue modulo
exactly when
is a quadratic residue modulo
, except when both primes are congruent to 3 modulo
4. The quadratic reciprocity theorem
proves this relation.