Law of Quadratic Reciprocity

Theorem

Let $p$ and $q$ be distinct odd primes.

Then:

$\displaystyle \left({\frac p q}\right) \left({\frac q p}\right) = \left({-1}\right)^{\frac {\left({p-1}\right) \left({q-1}\right)} 4}$

where $\displaystyle \left({\frac p q}\right)$ and $\displaystyle \left({\frac q p}\right)$ are defined as the Legendre symbol.

An alternative formulation is: $\displaystyle \left({\frac p q}\right) = \begin{cases} \quad \left({\dfrac q p}\right) & : p \equiv 1 \lor q \equiv 1 \pmod 4 \\ -\left({\dfrac q p}\right) & : p \equiv q \equiv 3 \pmod 4 \end{cases}$

The fact that these formulations are equivalent is immediate.

This fact is known as the Law of Quadratic Reciprocity, or LQR for short.

Proof

There are over 100 known proofs of this theorem, all of them fairly long.

Proof by Eisenstein

The following proof was discovered by Ferdinand Eisenstein and published in 1844.

Let $p$ and $q$ be distinct odd primes.

Consider the rectangle in the $x y$ plane with vertices at $\displaystyle \left({0, 0}\right), \left({\frac q 2, 0}\right), \left({\frac p 2, \frac q 2}\right), \left({0, \frac q 2}\right)$.

The number of lattice points inside this rectangle is $\displaystyle \frac {p-1} 2 \times \frac {q-1} 2$.

Consider the diagonal from $\left({0, 0}\right)$ to $\displaystyle \left({\frac p 2, \frac q 2}\right)$.

This has the equation $\displaystyle y = \frac q p x$.

Suppose there were a lattice point $\left({a, b}\right)$ on the diagonal.

Then $\displaystyle b = \frac q p a$.

But as $p$ and $q$ are distinct primes, this would mean $p$ divides $a$ and $q$ divides $b$.

This means that $\left({a, b}\right)$ has to be outside the rectangle.

So there are no lattice points on the diagonal inside the rectangle.

Let $A$ and $B$ be the triangular regions inside the rectangle lying respectively above and below the diagonal.

Let $\displaystyle k \in \Z: 0 < k < \frac p 2$.

The number of lattice points in $B$ which lie directly above the point $\left({k, 0}\right)$ is $\displaystyle \left \lfloor {\frac q p k}\right \rfloor$, where $\displaystyle \left \lfloor {\frac q p k}\right \rfloor$ is the floor function of $\displaystyle \frac q p k$.

So the total number of lattice points in $B$ is given by:

$\displaystyle N_B = \sum_{k=1}^{\frac{p-1}2} \left \lfloor {\frac q p k}\right \rfloor$.

Let $\alpha \left({q, p}\right)$ be defined as $\displaystyle \alpha \left({q, p}\right) = \sum_{k=1}^{\frac{p-1}2} \left \lfloor {\frac q p k}\right \rfloor$.

In the same way, by counting the lattice points to the right of $\left({0, k}\right)$, the total number of lattice points in $A$ is given by $N_A = \alpha \left({p, q}\right)$.

Now the total number of lattice points in the rectangle is $N_A + N_B$.

But this is also equal to $\displaystyle \frac {p-1} 2 \times \frac {q-1} 2 = \frac {\left({p-1}\right)\left({q-1}\right)} 4$.

So we have that $\displaystyle \alpha \left({p, q}\right) + \alpha \left({q, p}\right) = \frac {\left({p-1}\right)\left({q-1}\right)} 4$.

The fact that these counts are equal relies upon the fact that there are no lattice points on the diagonal, as demonstrated above.

Now we invoke the result Quadratic Nature by Sum of Floors of Multiples of Fractions‎, which is:

$\displaystyle \left({\frac a p}\right) = \left({-1}\right)^{\alpha \left({a, p}\right)}$.

So this gives us:

	\(\displaystyle \)	\(\displaystyle \left({\frac p q}\right) \left({\frac q p}\right)\)	\(=\)	\(\displaystyle \left({-1}\right)^{\alpha \left({p, q}\right)} \times \left({-1}\right)^{\alpha \left({q, p}\right)}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({-1}\right)^{\alpha \left({p, q}\right) + \alpha \left({q, p}\right)}\)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({-1}\right)^{\frac {\left({p-1}\right) \left({q-1}\right)} 4}\)	\(\displaystyle \)

which is LQR.

$\blacksquare$

Also see

• The First Supplement to the Law of Quadratic Reciprocity;
• The Second Supplement to the Law of Quadratic Reciprocity.

Sources

• 1844:  F.G. Eisenstein: Geometrischer Beweis des Fundamentaltheorems für die quadratischen Reste (J. Reine Angewandte Mathematik Vol. 28: 186 – 191)