# 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}{c}&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/