Law of Quadratic Reciprocity
In number theory, the law of quadratic reciprocity is a theorem about quadratic residues modulo an odd prime. The law allows us to determine whether congruences of the form mod have a solution, by giving a blueprint for computing the Legendre symbol for an odd prime and . For examples of explicit computations using the law of quadratic reciprocity, see Legendre Symbol. Quadratic reciprocity has applications in number theory and cryptography.
Statement of the Theorem
The theorem is most easily stated using Legendre symbols. The statement of the main theorem is
where and are odd prime numbers, and denotes the Legendre symbol.
There are two other results about Legendre symbols that are often grouped with the law of quadratic reciprocity and referred to as the first and second supplement to the law:
The first supplement is proved in the Legendre symbol page, and the second supplement is generally proved as a part of the proof of the main quadratic reciprocity law.
Gauss's Lemma
Most elementary proofs use Gauss's lemma on quadratic residues.
Lemma:
Suppose is an odd prime and . Then consider the distinct integers
Here, when we say " mod ," we refer to the smallest positive integer congruent to mod , i.e. the remainder upon division of by Let be the number of these integers that are larger than Then
- To evaluate , the integers in Gauss's lemma are , and two of these are larger than , so . And indeed mod , so is a square mod as expected.
- To evaluate , the integers in Gauss's lemma are , and three of these are larger than , so . So the congruence mod has no solutions.
Proof of the lemma:
Evaluate the product mod in two different ways. By rearranging terms, we get
But the product can also be evaluated by noticing that each of the distinct integers in Gauss's lemma is either or for , and showing that each of the 's is distinct. Multiplying them together mod gives multiplied by a number of minus signs, equal to the number of copies; but there are of these, so the sign is . The result follows by Euler's criterion and canceling the .
Proof of the Second Supplement
As an indication of the usefulness of Gauss's lemma in proving quadratic reciprocity, here is a computation of the symbol
- For , .
- For , .
So the number in Gauss's lemma is the number of in the second category, which is
- If , , so .
- If , , so .
- If , , so .
- If , , so .
So mod . But these are precisely the values of for which is even, so the second supplement follows.