The prime numbers, their properties, and their relation to the
composite numbers have fascinated mathematicians for thousands of
years. Yet it was not until the 1700s that the first really deep
result about prime numbers was discovered, by Leonhard Euler. The *Quadratic Reciprocity Theorem* was proved first by Gauss, in the
early 1800s, and reproved many times thereafter (at least eight times
by Gauss). We conclude our brief study of
number theory with a beautiful proof due to the brilliant young
mathematician Gotthold Eisenstein, who died tragically young, at 29,
of tuberculosis. The proof is similar to one by Gauss, but it replaces
a complicated lemma by an ingenious geometrical argument. This is a
good place to leave number theory, as it hints at the wonderful but
difficult and subtle areas of the subject; we hope it makes you want
to explore number theory further. See the bibliography for some
starting points.

Suppose $p$ is an odd prime and $p$ does not divide $b$. Then $b$ is a
**quadratic residue** (mod $p$) if
$b\equiv c^2 \pmod p$ for some $c$, and otherwise $b$ is a **quadratic nonresidue**. In other words, a
quadratic residue is a "perfect square'' in the world of modular
arithmetic.

It is easy to see that $x^2\equiv (p-x)^2\equiv (-x)^2$ for any $x$, so at most half of the elements of $\{1,2,3,\ldots,p-1\}$ are quadratic residues modulo $p$. It is also not hard to see that $x^2\equiv y^2$ implies that $y\equiv\pm x$, so in fact exactly half of the elements of $\{1,2,3,\ldots,p-1\}$ are quadratic residues.

It is convenient to have an easy and arithmetic way to identify
whether an element is a quadratic residue. It turns out to be most
useful to define a function $\hbox{QR}(b,p)=1$ if $b$ is a quadratic
residue mod $p$, and $\hbox{QR}(b,p)=-1$ otherwise. The standard
notation for this function is the **Legendre
symbol**:
$$\hbox{QR}(b,p)=\legendre{b}{p}.$$
We should emphasize here that the notation "QR'' is completely
non-standard, introduced in the hope that first writing this as a
function will make it easier to understand. The Legendre symbol is not
an ideal choice, since it looks exactly like a fraction, but as it is
the standard notation we will use it throughout the section.

Here is a theorem similar to Wilson's Theorem (3.10.3); in fact, Wilson's Theorem is a simple corollary of this theorem.

Theorem 3.12.1 If $p$ does not divide $b$ then $$(p-1)!\equiv -\legendre{b}{p}b^{(p-1)/2} \pmod p.$$

**Proof.**

Recall that for every $x\in\{1,2,3,\ldots,p-1\}$ there is a
unique $y\in\{1,2,3,\ldots,p-1\}$ such that $xy\equiv b$.
If $b$ is a quadratic residue then $y$ may be equal to $x$, but if
$b$ is a quadratic nonresidue then $y\not=x$.

Suppose that $b$ is a quadratic nonresidue. Then the numbers 1, 2, …, $p-1$ can be grouped into $(p-1)/2$ pairs $\{x_i,y_i\}$ with $x_iy_i \equiv b$. Thus $$(p-1)!=\prod_{i=1}^{(p-1)/2}x_iy_i\equiv b^{(p-1)/2} \pmod p.$$ Now suppose that $b$ is a quadratic residue. There are exactly two numbers in $\{1,2,\ldots,p-1\}$, say $c$ and $p-c$, such that $c^2\equiv(p-c)^2\equiv b$. The remaining $(p-3)/2$ numbers can be paired up as before. Then $$(p-1)!=c(p-c)\prod_{i=1}^{(p-3)/2}x_iy_i\equiv (pc-c^2)b^{(p-3)/2} \equiv(-b)b^{(p-3)/2}\equiv -b^{(p-1)/2},$$ where all congruences are $(\bmod\; p)$. This completes the proof.

Corollary 3.12.2 (Euler's Criterion) If $b$ is not divisible by $p$ then $$\legendre{b}{p}\equiv b^{(p-1)/2}\pmod p.$$

**Proof.**

Using Wilson's Theorem 3.10.3
and Theorem 3.12.1,
$$-1\equiv (p-1)! \equiv -\legendre{b}{p}b^{(p-1)/2},$$
so
$$1\equiv \legendre{b}{p}b^{(p-1)/2}.$$
This implies the desired congruence.

Now we are ready for the principal result. Until now, we have used the notation "mod'' only in a context like $a\equiv b\pmod n$. There is another common use of this notation; fortunately it is closely related to the first. If we refer to "$a\bmod n$,'' we mean the remainder when $a$ is divided by $n$, that is, the unique remainder in $\{0,1,\ldots,n-1\}$. For example, $(25\bmod 11)$ is $3$.

Theorem 3.12.3 (Quadratic Reciprocity Theorem) If $p$ and $q$ are distinct odd primes, then $$\legendre{p}{q}\legendre{q}{p}=(-1)^{((p-1)/2)((q-1)/2)}.$$

**Proof.**

Let $E=\{2,4,6,\ldots,p-1\}$ and $r_e=eq \bmod p$. We claim
that
$$\{(-1)^{r_e}r_e \bmod p : e\in E\}=E.
$$
First, we note that if
$r_e$ is even then $(-1)^{r_e}r_e=r_e$ is even, and if $r_e$ is odd
then $(-1)^{r_e}r_e=-r_e$, so $(-1)^{r_e}r_e \bmod p = p-r_e$, which
is even. Thus, $\{(-1)^{r_e}r_e \bmod p : e\in E\}\subseteq E$. The
set $\{(-1)^{r_e}r_e \bmod p : e\in E\}$ can fail to be equal to $E$
only if $(-1)^{r_e}r_e\equiv (-1)^{r_f}r_f \pmod p$ for two distinct
elements $e$ and $f$ in $E$. This implies that
$(-1)^{r_e}qe\equiv(-1)^{r_f}qf$, which implies that $e\equiv\pm
f$. Since $e$ and $f$ are distinct, $e\equiv-f$ or $e+f\equiv 0$, that
is, $p|e+f$. But $0< e+f< 2p$, and $e+f$ is even while $p$ is odd, so
this is impossible. This contradiction implies the claim.

Now $$q^{(p-1)/2}\prod_{e\in E} e=\prod_{e\in E} qe\equiv \prod_{e\in E} r_e$$ and $$\prod_{e\in E} e\equiv \prod_{e\in E} (-1)^{r_e}r_e= (-1)^{\Sigma r}\prod_{e\in E}r_e,$$ where $\sum r=\sum_{e\in E} r_e$. Hence, $$q^{(p-1)/2}(-1)^{\Sigma r}\prod_{e\in E}r_e\equiv\prod_{e\in E}r_e, $$ which implies that $q^{(p-1)/2}\equiv(-1)^{\Sigma r}$. By Euler's Criterion, $\legendre{q}{p}=(-1)^{\Sigma r}$. Since the value of $(-1)^{\Sigma r}$ is determined by the parity of $\sum_{e\in E} r_e$, we can replace $\sum_{e\in E} r_e$ by any number of the same parity without changing $(-1)^{\Sigma r}$.

Note that $$\sum_{e\in E}qe=\sum_{e\in E}\left(p\left\lfloor qe/p\right\rfloor+r_e\right)=p\sum_{e\in E}\lfloor qe/p\rfloor + \sum_{e\in E}r_e, $$ so $\sum_{e\in E}\lfloor qe/p\rfloor$ has the same parity as $\sum_{e\in E}r_e$. (Recall that the floor function $\lfloor\>\rfloor$ means to round down to the nearest integer.)

In what follows we refer to this diagram of a portion of the first quadrant:

The **integer lattice points** are the points in the plane
with two integer coordinates; we are interested in the integer lattice
points inside rectangle $AFBD$, *not* including those on the
edges. In the diagram, we show the integer lattice points using $p=17$
and $q=11$.

Because $p$ and $q$ are prime, there are no integer lattice points on the line $AB$. For any $e\in E$, the point $(e,qe/p)$ is on the line $AB$, so the number of integer lattice points inside triangle $ABD$ with abscissa $e$ is $\lfloor qe/p\rfloor$, and $\sum_{e\in E}\lfloor qe/p\rfloor$ is the number of integer lattice points in $ABD$ with even abscissas; these are shown in green in the diagram.

The number of integer lattice points inside rectangle $ADBF$ with a given integer abscissa is even (namely, $q-1$), so the number of these points above line $AB$ has the same parity as the number below $AB$. Suppose $e\in E$ and $e>p/2$. The number of integer lattice points with abscissa $e$ above line $AB$ is the same as the number of integer lattice points with abscissa $p-e$ below $AB$; these points are shown in red. Since $p-e$ is odd, $$\eqalign{\sum_{e\in E}\left\lfloor{ qe\over p}\right\rfloor&= \sum_{e< p/2}\left\lfloor{ qe\over p}\right\rfloor+ \sum_{e>p/2}\left\lfloor{ qe\over p}\right\rfloor\cr &\equiv \sum_{e< p/2}\left\lfloor{ qe\over p}\right\rfloor+ (\hbox{the number of points with even abscissa in $HJB$})\cr &=\sum_{e< p/2}\left\lfloor{ qe\over p}\right\rfloor+ (\hbox{the number of points with odd abscissa in $AKH$}) \cr &= (\hbox{the number of lattice points in $AKH$})\cr &\doteq \mu,\cr} $$ where the congruence on the second line is $(\hbox{mod} 2)$. (The symbol $\doteq$ indicates that we are defining a new variable $\mu$ equal to the number of lattice points in $AKH$.) So $\mu$ has the same parity as $\sum_{e\in E} r_e$, and $\legendre{q}{p}=(-1)^\mu$. By precisely the same argument, $\legendre{p}{q}=(-1)^\nu$, where $\nu$ is the number of integer lattice points in $ALH$. Since there are $((p-1)/2)((q-1)/2)$ integer lattice points in rectangle $AKHL$, we have $$\legendre{p}{q}\legendre{q}{p}=(-1)^{\mu+\nu}=(-1)^{((p-1)/2)((q-1)/2)}, $$ as promised.

**Ferdinand Gotthold Max Eisenstein.**
Eisenstein (1823-1852) was born to parents of limited means and
remained near poverty throughout his life. He had five younger
siblings, all of whom died in childhood—most of meningitis, which
also afflicted Eisenstein. He suffered from poor health and depression
for most of his life.

Eisenstein first became interested in mathematics when he was six, thanks to a family acquaintance. In his autobiography, Eisenstein wrote, "As a boy of six I could understand the proof of a mathematical theorem more readily than that meat had to be cut with one's knife, not one's fork.'' He also had a lifelong interest in music—he played the piano and composed.

Eisenstein had some excellent and encouraging teachers in mathematics,
and began reading the work of Euler, Lagrange and Gauss at an early
age. In 1843 he passed his secondary school examinations, though he
already knew far more mathematics than the standard secondary fare. He
enrolled at the University of Berlin and submitted his first paper in
January of 1844. In that year, volumes 27 and 28 of Crelle's
mathematical journal contained *twenty-five* works by
Eisenstein, making him an overnight sensation in mathematical circles.
Gauss was very impressed by Eisenstein's early work, and wrote the
preface for an 1847 collection of work by Eisenstein.

Through Crelle, Eisenstein met Alexander von Humboldt, who became his mentor, champion and financial lifeline. Humboldt secured a series of small grants for Eisenstein, and sometimes contributed his own funds to help Eisenstein through times between grants.

Eisenstein was minimally involved in the political unrest of 1848. He was arrested and detained overnight, suffering severe mistreatment that hurt his already poor health. The incident also made it even more difficult for him to find financial support; Humboldt was just barely able to find some funding for him. Eisenstein's health deteriorated and his depression increased, so that he was often unable to deliver his lectures, but he continued to publish papers.

In 1851 Eisenstein was elected to the Göttingen Society, and in 1852 to the Berlin Academy. In July of 1852, his health declined precipitously when he suffered a hemorrhage. Humboldt raised enough money to send him to recuperate in Italy for a year, but it came too late. Eisenstein died in October of tuberculosis.

Our exposition of Eisenstein's proof is taken from *Eisenstein's
Misunderstood Geometric Proof of the Quadratic Reciprocity Theorem*,
by Reinhard Laubenbacher and David Pengelley, in **The College
Mathematics Journal**, volume 25, number 1, January 1994. Biographical
information is from the same paper, and from the article on Eisenstein,
by Kurt-R. Biermann, in **Biographical Dictionary of
Mathematicians**, New York: Charles Scribner's Sons, 1991.

## Exercises 3.12

**Ex 3.12.1**
Verify the quadratic reciprocity theorem directly for the
following pairs of primes. That is, compute $\legendre{q}{p}$ and
$\legendre{p}{q}$ directly by determining whether or not each is a
quadratic residue modulo the other, and then check that the theorem is
satisfied.

a) 5, 11

b) 3, 19

**Ex 3.12.2**
Prove that $x^2\equiv y^2\pmod p$ implies that $y\equiv\pm
x\pmod p$, for prime $p$. Hint:
look at the proof of Theorem 3.10.1.

**Ex 3.12.3**
Prove Wilson's Theorem 3.10.3
from Theorem 3.12.1.

**Ex 3.12.4**
Explain why Euler's Criterion is implied by the last
congruence in the proof of Corollary 3.12.2.

**Ex 3.12.5**
Prove that there are no integer lattice points on $AB$.

**Ex 3.12.6**
Prove that the number of integer lattice
points with abscissa $e$ above line $AB$ is the same as the number of
integer lattice points with abscissa $p-e$ below $AB$.

**Ex 3.12.7**
The Quadratic Reciprocity Theorem can be restated in
a different, perhaps more appealing, way:

Suppose $p$ and $q$ are distinct odd primes. Then $p$ and $q$ are each quadratic residues of the other, or are each quadratic non-residues of the other, unless both $(p-1)/2$ and $(q-1)/2$ are odd.

Prove this version of the theorem, using theorem 3.12.3.