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$ 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. $\qed$
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.$\qed$
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 in the diagram. 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.$\qed$
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.