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 \( x^2 \equiv a \) mod \( p \) have a solution, by giving a blueprint for computing the Legendre symbol \( \big( \frac{a}{p}\big) \) for \( p \) an odd prime and \( p \nmid a \). 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
\[\large \left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2} },\]
where \(p\) and \(q\) are odd prime numbers, and \(\left(\frac{p}{q}\right)\) 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:
\[\left(\dfrac{-1}{p}\right) = (-1)^{\frac{p-1}2}, \qquad \left(\dfrac{2}{p}\right) = (-1)^{\frac{p^2-1}8}.\]
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 \( p \) is an odd prime and \( p \nmid a \). Then consider the \( \frac{p-1}2 \) distinct integers
\[\begin{array} &a ~\text{ mod } p, &2a ~\text{ mod } p, &\ldots, &\left(\frac{p-1}2\right)a ~\text{ mod } p.\end{array} \]
\((\)Here, when we say "\( b \) mod \( p \)," we refer to the smallest positive integer congruent to \( b \) mod \( p \), i.e. the remainder upon division of \( b \) by \( p.)\) Let \(n\) be the number of these integers that are larger than \( \frac p2.\) Then
\[ \left( \dfrac{a}{p} \right) = (-1)^n.\]
- To evaluate \( \left( \frac{3}{11} \right) \), the integers in Gauss's lemma are \( 3,6,9,1,4 \), and two of these are larger than \(\frac{11}2\), so \( \left( \frac{3}{11}\right) = (-1)^2 = 1 \). And indeed \( 5^2 \equiv 3 \) mod \( 11 \), so \( 3 \) is a square mod \( 11,\) as expected.
- To evaluate \( \left( \frac{3}{19} \right) \), the integers in Gauss's lemma are \( 3,6,9,12,15,18,2,5,8 \), and three of these are larger than \(\frac{19}2 \), so \( \left( \frac{3}{19}\right) = (-1)^3 = -1\). So the congruence \( x^2 \equiv 3 \) mod \( 19 \) has no solutions.
Proof of the lemma:
Evaluate the product \( a \cdot 2a \cdots \frac{p-1}2 a \) mod \( p \) in two different ways. By rearranging terms, we get
\[ a^{\frac{p-1}2} \left( \frac{p-1}2 \right)!. \]
But the product can also be evaluated by noticing that each of the distinct integers in Gauss's lemma is either \( x \) or \( p-x \) for \( 1 \le x \le \frac{p-1}2 \), and showing that each of the \( x\)'s is distinct. Multiplying them together mod \( p \) gives \( \left( \frac{p-1}2 \right)! \) multiplied by a number of minus signs, equal to the number of \( p-x \) copies; but there are \( n \) of these, so the sign is \( (-1)^n \). The result follows by Euler's criterion and canceling the \( \left(\frac{p-1}2\right)! \). \(_\square\)
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 \( \left( \frac{2}{p}\right): \)
- For \( 1 \le a \le \left\lfloor \frac p4 \right\rfloor \), \( 2a < \frac p2 \).
- For \( \left\lfloor\frac p4 + 1 \right\rfloor \le a \le \frac{p-1}2 \), \(\frac p2 < 2a < p \).
So the number \( n \) in Gauss's lemma is the number of \( a \) in the second category, which is \( \frac{p-1}2 - \left\lfloor\frac p4 \right\rfloor: \)
- If \( p =8k+1\), \( n = 2k \), so \( \left( \frac{2}{p} \right) = (-1)^{2k} = 1 \).
- If \( p =8k+3\), \( n = 2k+1 \), so \( \left( \frac{2}{p} \right) = (-1)^{2k+1} = -1 \).
- If \( p =8k+5\), \( n = 2k+1 \), so \( \left( \frac{2}{p} \right) = (-1)^{2k+1} = -1 \).
- If \( p =8k+7\), \( n = 2k+2 \), so \( \left( \frac{2}{p} \right) = (-1)^{2k+2} = 1 \).
So \( \left( \frac{2}{p} \right) = 1 \Longleftrightarrow p \equiv \pm 1 \) mod \( 8 \). But these are precisely the values of \( p \) for which \( \frac{p^2-1}8 \) is even, so the second supplement follows. \(_\square \)