Fermat’s remarkable discovery that odd primes of the quadratic form $x^{2}+y^{2}$ are in fact those of the linear form $4 n+1$ led to the more general problem of describing primes of the form $x^{2}+d y^{2}$ for nonsquare integers $d$. Is it true, for each $d$, that the primes of the form $x^{2}+d y^{2}$ are those of a finite number of linear forms?
Fermat found such forms for the primes $x^{2}+2 y^{2}$ and $x^{2}+3 y^{2}$ as well. In each case a crucial step in determining the linear forms of the primes $x^{2}+d y^{2}$ is to find the quadratic character of $-d$, that is, to find the primes $q$ such that $-d$ is a square, $\bmod q$.
The law of quadratic reciprocity answers all such questions. The law describes when $p$ is a square, $\bmod q$, for odd primes $p$ and $q$; and its supplements deal with the cases $p=-1$ and $p=2$.
To prove it, we first prove Euler’s criterion, which states that $p$ is a square mod $q \Leftrightarrow p^{\frac{q-1}{2}} \equiv 1(\bmod q)$. This yields the supplements fairly easily, and it also helps in the proof of the law itself.
We also need the Chinese remainder theorem. It is of interest in itself and for what it says about the Euler $\varphi$ function, but our main purpose is to use it to prove quadratic reciprocity for odd primes $p$ and $q$.
To discuss quadratic reciprocity tersely we use Legendre’s symbol $\left(\frac{p}{q}\right)$, which equals 1 when $P$ is a square $\bmod q$, and $-1$ otherwise. All values of $\left(\frac{p}{q}\right)$ follow from the values $\left(\frac{p}{q}\right)$ for odd primes $p$ (from quadratic reciprocity) and the special values $\left(\frac{-1}{q}\right)$ and $\left(\frac{2}{q}\right)$ (from the supplements).
Primes $x^{2}+y^{2}, x^{2}+2 y^{2}$, and $x^{2}+3 y^{2}$
The primes $x^{2}+y^{2}$ again
In the proof of Fermat’s two square theorem, that an odd prime $p$ is of the form $x^{2}+y^{2}$ if and only if $p$ is of the form $4 n+1$, a key step was showing that any prime $p=4 n+1$ divides a number of the form $m^{2}+1$. We proved this in Section $6.5$ using Wilson’s theorem to construct a suitable $m .$
We now re-examine this step to see how it might be generalized. The statement that $p$ divides $m^{2}+1$ is equivalent to
$$
-1 \equiv m^{2} \quad(\bmod p)
$$
in other words $-1$ is a square, $\bmod p=4 n+1$. And indeed our proof was to take the expression for $-1$ given by Wilson’s theorem and show that it was in fact a square, $\bmod p=4 n+1$
This raises the general question of whether $q$ is a square mod $p$, where $p$ and $q$ are arbitrary integers. We also state the question as: what is the quadratic character of $q, \bmod p ?$ Several problems lead to this question, as we now show.
The form $x^{2}+2 y^{2}$
After describing the primes of the form $x^{2}+y^{2}$, Fermat tackled primes of the form $x^{2}+2 y^{2}$. He claimed that
$$
p=x^{2}+2 y^{2} \Leftrightarrow p=8 n+1 \text { or } p=8 n+3
$$
A proof can be given along the same lines as our proof of the two square theorem.
We work in $\mathbb{Z}[\sqrt{-2}]$, and prove first that if $p$ is an ordinary prime that is not a prime of $\mathbb{Z}[\sqrt{-2}]$ then
$$
p=a^{2}+2 b^{2} \quad \text { for some } a, b \in \mathbb{Z}
$$
The proof is like that for non-Gaussian primes (Section 6.3). If $p$ is not a prime of $\mathbb{Z}[\sqrt{-2}]$ then it has factors of norm $>1$, say
$$
p=(a+b \sqrt{-2}) \gamma
$$
Multiplying this equation by its conjugate leads to $p=a^{2}+2 b^{2}$
The key step now is to prove that any prime $p=8 n+1$ or $8 n+3$ divides a number of the form $m^{2}+2$. Once this is done, one uses the factorization
$$
m^{2}+2=(m-\sqrt{-2})(m+\sqrt{-2})
$$
and unique prime factorization in $\mathbb{Z}[\sqrt{-2}]$ to complete the proof as we did for $\mathbb{Z}[i]$ (Section 6.5).
The claim that $p$ divides a number of the form $m^{2}+2$ is equivalent to
$$
-2 \equiv m^{2} \quad(\bmod p)
$$
Thus we have to prove that $-2$ is a square, $\bmod p$, when $p$ is a prime of the form $8 n+1$ or $8 n+3$
The form $x^{2}+3 y^{2}$
Next, Fermat described the primes of the form $x^{2}+3 y^{2}$
$$
p=x^{2}+3 y^{2} \Leftrightarrow p=3 n+1
$$
This can be proved along the same lines as for $x^{2}+y^{2}$ and $x^{2}+2 y^{2}$, this time using factorizations in $\mathbb{Z}\left[\frac{-1+\sqrt{-3}}{2}\right]$. The awkward step is to prove that any prime $p=3 n+1$ divides a number of the form $m^{2}+3$. Equivalently,
$$
-3 \equiv m^{2} \quad(\bmod p)
$$
so we now have to prove that $-3$ is a square, $\bmod p=3 n+1$
Statement of quadratic reciprocity
In the mid-18th century Euler realized that knowing the primes of forms such as $x^{2}+y^{2}, x^{2}+2 y^{2}$ and $x^{2}+3 y^{2}$ depends on knowing whether $p$ is a square $\bmod q$, for certain integers $p$ and $q .$ In the case where $p$ and $q$ are both odd primes he conjectured that the answer is:
When $p$ and $q$ are both of the form $4 n+3$, then
$p$ is a square, $\bmod q \Leftrightarrow q$ is not a square, $\bmod p$.
Otherwise
$p$ is a square, $\bmod q \Leftrightarrow q$ is a square, $\bmod p$.
Because of the reciprocal relationship between $p$ and $q$, this statement is called the law of quadratic reciprocity. (The word “quadratic” in this case really means “square”. In the literature one often finds the old term “quadratic residues $\bmod p$ ” for “squares $\bmod p “$.)
Euler was unable to prove the law of quadratic reciprocity. The first proofs were given by Gauss in 1801 . Since then nearly 200 different proofs have been given, making quadratic reciprocity the second most proved theorem in mathematics, after Pythagoras’ theorem.
Euler’s criterion
If $q$ is prime and $a \not \equiv 0(\bmod q)$, then $a^{q-1} \equiv 1(\bmod q)$ by Fermat’s little theorem. Euler used this to derive the following formula:
Euler’s criterion. For an odd prime $q,\left(\frac{p}{q}\right) \equiv p^{\frac{q-1}{2}}(\bmod q)$, and hence $p$ is a square mod $q \Leftrightarrow p^{\frac{q-1}{2}} \equiv 1(\bmod q)$。
Proof. First suppose that $p$ is a square mod $q$, say $p \equiv a^{2}(\bmod q)$. Then $\left(\frac{p}{q}\right)=1$ by definition and
$$
p^{\frac{q-1}{2}} \equiv a^{q-1} \equiv 1 \quad(\bmod q) \quad \text { by Fermat’s little theorem. }
$$
Conversely, if $p$ is not a square mod $q$, it suffices to show that
$$
p^{\frac{q-1}{2}} \not \equiv 1 \quad(\bmod q)
$$
This is so because $x=p^{\frac{q-1}{2}}$ satisfies $x^{2} \equiv p^{q-1} \equiv 1(\bmod q)$ by Fermat’s little theorem, and $x^{2} \equiv 1$ has only the two solutions $x \equiv \pm 1$ by Lagrange’s polynomial congruence theorem.
By the same theorem, $p^{\frac{q-1}{2}} \equiv 1(\bmod q)$ has at most $\frac{q-1}{2}$ solutions, and we know that they include the squares $p=1^{2}, 2^{2}, \ldots,\left(\frac{q-1}{2}\right)^{2}$. These $\frac{q-1}{2}$ squares are distinct. Indeed, if $x^{2}$ and $y^{2}$ are any two of them we have
$$
\begin{aligned}
x^{2} \equiv y^{2}(\bmod q) & \Rightarrow x^{2}-y^{2} \equiv 0 \quad(\bmod q) \
& \Rightarrow(x-y)(x+y) \equiv 0 \quad(\bmod q) \
& \Rightarrow x=y
\end{aligned}
$$
This is so because $1<x+y<q$ and hence $x+y \not \equiv 0(\bmod q)$.
Thus when $p \not \equiv a^{2}(\bmod q)$ we have $p^{\frac{q-1}{2}} \neq 1(\bmod q)$ and therefore $p^{\frac{q-1}{2}} \equiv-1 \equiv\left(\frac{p}{q}\right)(\bmod q)$
Notice that the proof of this criterion does not assume that $p$ is actually prime. We take this opportunity to define $\left(\frac{p}{q}\right)$, for any $P \not \equiv 0(\bmod q)$, to be 1 if $P$ is a square mod $q$ and $-1$ otherwise. Then the Euler criterion gives an easy proof of the following.
Multiplicative property of $\left(\frac{p}{q}\right) .$ For any $P_{1}, P_{2} \not \equiv 0(\bmod q)$
$$
\left(\frac{P_{1}}{q}\right)\left(\frac{P_{2}}{q}\right)=\left(\frac{P_{1} P_{2}}{q}\right)
$$
Proof of quadratic reciprocity
A formula for $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$
We now give a formula that simultaneously exhibits $\left(\frac{p}{q}\right)$ and $\left(\frac{q}{p}\right)$ in a product of pairs $(\bmod p, \bmod q)$. This formula is used to prove quadratic reciprocity below, following the argument of Rousseau (1991).
Completion of the proof
Now we evaluate $\Pi(x, x)$ over the invertible $x$ in a different way, expressing it in powers of $-1$ alone. Using the Chinese remainder theorem, we view it as a product of pairs $(a, b)$, with $a$ and $b$ varying independently over suitable ranges.
The $x$ in the range $1 \leq x \leq \frac{p q-1}{2}$ include exactly one number from each pair ${x,-x}(\bmod p q)$ with $1 \leq x \leq p q-1$. Hence the corresponding remainder pairs,
$$
(a, b)=(x \bmod p, x \bmod q)
$$
include exactly one of each pair ${(a, b),(-a,-b)}$. We get exactly one of each $(\bmod p, \bmod q)$ by taking the ranges $1 \leq a \leq p-1$ and $1 \leq b \leq \frac{q-1}{2}$
This makes the sign uncertain, but at any rate
$$
\prod_{1 \leq x \leq \frac{p q-1}{2}}^{\text {invertible } x}(x, x) \equiv \pm\left((p-1) !^{\frac{q-1}{2}},((q-1) / 2) !^{p-1}\right) \quad(\bmod p, \bmod q)
$$
since each value of $a, 1 \leq a \leq p-1$, occurs in $(q-1) / 2$ pairs, and each value of $b, 1 \leq b \leq(q-1) / 2$, occurs in $p-1$ pairs. Thanks to Wilson’s theorem, we can express the powers of factorials in (2) as powers of $-1$
Since $(p-1) ! \equiv-1(\bmod p)$, the first component $\equiv(-1)^{\frac{q-1}{2}}(\bmod p)$ To find $((q-1) / 2) !(\bmod q)$ we shape $-1 \equiv(q-1) !$ as in Section 6.5:
$$
\begin{aligned}
-1 \equiv &(q-1) ! \quad(\bmod q) \
\equiv & 1 \times 2 \times \cdots \times((q-1) / 2) \
& \times(-(q-1) / 2) \times \cdots \times(-2) \times(-1) \quad(\bmod q) \
\equiv &((q-1) / 2) !^{2}(-1)^{\frac{q-1}{2}} \quad(\bmod q)
\end{aligned}
$$
Therefore
$$
((q-1) / 2) !^{2} \equiv(-1)(-1)^{\frac{q-1}{2}} \quad(\bmod q)
$$
Raising both sides to the power $\frac{p-1}{2}$, we get the second component of $(2)$
$$
((q-1) / 2) !^{p-1} \equiv(-1)^{\frac{p-1}{2}}(-1)^{\frac{p-1}{2} \frac{q-1}{2}}(\bmod q)
$$
Thus the expression (2) for $\Pi(x, x)(\bmod p, \bmod q)$, reduces to
$$
\prod_{1 \leq x \leq \frac{p q-1}{2}}^{\text {invertible } x}(x, x) \equiv \pm\left((-1)^{\frac{q-1}{2}},(-1)^{\frac{p-1}{2}}(-1)^{\frac{p-1}{2} \frac{q-1}{2}}\right) \quad(\bmod p, \bmod q)
$$
Equating (3) with (1) in the previous subsection we get either
$$
\left(\frac{q}{p}\right)=1 \quad \text { and } \quad\left(\frac{p}{q}\right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}
$$
or
$$
\left(\frac{q}{p}\right)=-1 \quad \text { and } \quad\left(\frac{p}{q}\right)=-(-1)^{\frac{p-1}{2} \frac{q-1}{2}}
$$
In either case,
$$
\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2} \frac{q-1}{2}}
$$
Discussion
The first to attempt a general proof was Legendre (1785). However, his proof depended on the unproved assumption that any arithmetic progression $a n+b$ with $\operatorname{gcd}(a, b)=1$ contains infinitely many primes. This assumption is easily proved in certain cases but the
general theorem is harder to prove than reciprocity itself. The first proof
was given by Dirichlet (1837), and the deep analytic methods he devised to
prove it are still the standard approach to primes in arithmetic progressions.
Gauss found the first proof of quadratic reciprocity on April 18,1796, when he was not quite 19 . It is a long and ugly proof, and by the time he published it in his Disquisitiones Arithmeticae of (1801) he had found two nore proofs; one using quadratic forms and the other using roots of unity. Quadratic reciprocity was Gauss’s favorite theorem and altogether he gave broofs-some of them variations or simplifications of Gauss, and others ntroducing new ideas.
Like Pythagoras’ theorem in geometry, quadratic reciprocity is a core fuadratic Diophantine equations. This is why the theorem has so many broofs: all roads lead to it, and each road shows it from a different angle. A comprehensive history of quadratic reciprocity, including a table and :lassification of 196 (!) proofs given up to the year 2000 , may be found n Lemmermeyer (2000). Another book of interest is Pieper (1978), which liscusses 14 different proofs in detail.
The law of quadratic reciprocity generalizes to cubic, biquadratic, and higher power reciprocity laws. Just as the quadratic character has values $\pm 1$ (the square roots of 1 ), there is a cubic character with values $1, \zeta_{3}$, $\zeta_{3}^{2}$ (the cube roots of 1 ), and a biquadratic character with values $\pm 1, \pm i$ the fourth roots of 1 ). These generalizations were not made because mathematicians had run out of things to say about quadratic forms – quite the contrary; quadratic forms themselves demand that cubes and fourth powers e considered. This was discovered by Euler, who noticed the following esults (later proved by Gauss):
$p$ is a prime $x^{2}+27 y^{2} \Leftrightarrow p=3 n+1$ and 2 is a cube mod $p$ $p$ is a prime $x^{2}+64 y^{2} \Leftrightarrow p=4 n+1$ and 2 is a fourth power mod $p$
The cubic reciprocity law was found by Eisenstein (1844) and it rejuires investigation of $\mathbb{Z}\left[\zeta_{3}\right]$, which is why we call $\mathbb{Z}\left[\zeta_{3}\right]$ the Eisenstein ntegers. (Cubic reciprocity was already known to Gauss, but he did not bublish his results.) Likewise, biquadratic reciprocity was discovered by Gauss and it requires investigation of $\mathbb{Z}[i]$. This in fact was the purpose of Gauss (1832), where the basic properties of $\mathbb{Z}[i]$ were first published.
