# 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 \( \left( \dfrac{a}{p}\right) \) 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(\dfrac{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:
\[
\begin{align}
\left(\dfrac{-1}{p}\right) &= (-1)^{\frac{p-1}2} \\
\left(\dfrac{2}{p}\right) &= (-1)^{\frac{p^2-1}8}.
\end{align}
\]
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 \( p/2 \). 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 \( 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 \( 19/2 \), so \( \left( \frac{3}{19}\right) = (-1)^3 = -1\). So the congruence \( x^2 \equiv 3 \) mod \( 19 \) has no solutions.

\[\large\sum_{n=1}^{10007}\left(\frac{n(n+1)}{10009}\right) = \, ?\]

**Note:** In above summation expression , \(\large \left( \frac{a}{b} \right) \) denotes the Legendre symbol and it is **not** an ordinary fraction.

**Bonus:** Generalize this for arbitary odd primes.

**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)! \).

## 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 \lfloor p/4 \rfloor \), \( 2a < p/2 \).

For \( \lfloor p/4 + 1 \rfloor \le a \le \frac{p-1}2 \), \( p/2 < 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 - \lfloor p/4 \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 \Leftrightarrow 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 \)

## See also

**Cite as:**Law of Quadratic Reciprocity.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/law-of-quadratic-reciprocity/