# 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 \)

## See Also

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

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