Some proofs of the quadratic reciprocity law

Gauss's quadratic reciprocity law is a mysterious relation between prime numbers. If $p$ and $q$ are distinct prime numbers, it shows that there is a relation between the property that $p$ is a square modulo $q$, and the property that $q$ is a square modulo $p$: both are not independent. Gauss has given many proofs of this law, the first two of them were published in his 1801 Disquisitiones arithmeticae. Franz Lemmermeyer references 246 proofs of the quadratic reciprocity law on his website! In his book Reciprocity laws, from Eisenstein to Kronecker, he adds that “modern number theory dates from the discovery of the reciprocity law” (preface, p. v).

In this post, I want to discuss a few proofs of this law, that will range to the most basic to the most elaborate. But first, the statement.

Stating the quadratic reciprocity law

If $p$ is an odd prime number, we denote by $\mathbf F_p$ the field with $p$ elements. In this field, exactly half of the nonzero elements are squares. This is embodied in the following exact sequence of abelian groups:
$$1 \to \{\pm1\} \to \mathbf F_p^\times \xrightarrow{a\mapsto a^2} \mathbf F_p^\times \xrightarrow {a\mapsto a^{(p-1)/2}} \{\pm1\} \to 1 .$$
This means that the image of every morphism is the kernel of the next one. In explicit terms:

1. Squares are the image of the map $a\mapsto a^2$ whose kernel is $\{\pm1\}$;
2. An element $a\in\mathbf F_p^\times$ is a square if and only if $a^{(p-1)/2}=1$; otherwise, $a^{(p-1)/2}=-1$.

To prove that this is indeed an exact sequence, we work left to right. The kernel of $a\mapsto a^2$ consists exactly of $\{\pm1\}$; the cardinality of the image of this map, the squares,  is thus equal to $(p-1)/2$. If $a\in\mathbf F_p^\times$, one has $(a^{(p-1)/2})^2=a^{p-1}=1$, by Fermat's little theorem, so that the image of $a\mapsto a^{(p-1)/2}$ is contained in $\{\pm1\}$. If $a$ is a square, writing $a=b^2$, one has $a^{(p-1)/2}=b^{p-1}=1$, so that the squares are contained in the kernel of this morphism. On the other hand, there are at most $(p-1)/2$ elements $a\in \mathbf F_p^\times$ such that $a^{(p-1)/2}=1$, and the squares account for all of them, so that non squares satisfy $a^{(p-1)/2}=-1$.

For $a\in\mathbf F_p$, or even $a\in\mathbf Z$, one classically denotes by $(\frac ap)$ the element of $\{0,1,-1\}$ which is equal to expression $a^{(p-1)/2}$ in $\mathbf F_p$. This is the Legendre symbol of $a$ modulo $p$.

Let now $q$ be another odd prime number. We can consider the Legendre symbols $(\frac qp)$ and $(\frac qp)$ of $q$ modulo $p$ and of $p$ modulo $q$. Thise are elements of $\{\pm1\}$ and the quadratic reciprocity law states:
$$\big(\frac pq\big) \, \big(\frac qp\big) = (-1)^{(p-1)(q-1)/4}.$$
Since this may look frightening, let us make this slightly more explicit:

1. If $p$ or $q$ is congruent to $1$ modulo $4$, then $p$ is a square modulo $q$ exactly when $q$ is a square modulo $p$.
2. If $p$ and $q$ both are congruent to $3$ modulo $4$, then $p$ is a square modulo $q$ exactly when $q$ is not a square modulo $p$.

This property may be used to compute Legendre symbols relatively quickly, by successive euclidean divisions.

The complementary laws

A few particular cases are either important, or classical enough to deserve being quoted. They may also have relatively easier proofs which already indicate a relation between the quadratic reciprocity law and roots of unity.

$-1$ is a square modulo $p$ if and only if $p\equiv 1\pmod 4$.

Indeed, $(\frac{-1}p)=(-1)^{(p-1)/2}$, which is $1$ if and only if $(p-1)/2$ is even, that is $p\equiv 1\pmod 4$. A possibly simple way to understand this is the following: $-1$ is a square in $\mathbf F_p^\times$ if and only if there are elements of order $4$ in $\mathbf F_p^\times$, which is equivalent to the divisibility $4\mid p-1$ because the group $\mathbf F_p^\times$ is cyclic.

$-3$ is a square modulo $p$ if and only if $p \equiv 1\pmod 3$.

Indeed, the usual formula for the cubic roots of unity $(-1\pm i \sqrt 3)/2$ shows that $-3$ is a square modulo $p$ if and only if there are elements of order 3 in $\mathbf F_p^\times$, that is, if and only if $3\mid p-1$.

$3$ is a square modulo $p$ if and only if $p\equiv \pm1 \pmod{12}$.

Indeed, the formula $(\frac 3p)=(\frac{-1}p)(\frac{-3}p)$ shows that $3$ is a square modulo $p$ if and only if either $-3$ and $-1$ both are squares modulo $p$, or both are non-squares modulo $p$. The first case holds when $p\equiv 1\pmod 3$ and $p\equiv 1\pmod 4$, that is, $p\equiv 1\pmod{12}$; the second case holds when $p\equiv -1\pmod3$ and $p\equiv-1\pmod4$, that is, $p\equiv-1\pmod{12}$.

$2$ is a square modulo $p$ if and only if $p\equiv \pm1\pmod 8$.

We play the same game with octic roots of unity, classically given by $(\pm 1+\pm i)/\sqrt 2$. So if $-1$ and $2$ are squares modulo $p$, then there exists an octic root of unity in $\mathbf F_p$, and $p\equiv 1\pmod 8$, and conversely. In the case $p\equiv 1\pmod 4$, this show that $2$ is a square modulo $p$ if and only if $p\equiv 1\pmod 8$.

On the other hand, one has $p^2\equiv 1\pmod8$, whatever odd prime number $p$ is, so that there exists an octic root of unity $\omega$ in the field $\mathbf F_{p^2}$ with $p^2$ elements. The question is whether $\omega$ belongs to $\mathbf F_p$. This is settled by Fermat's little theorem again: it holds if and only if $\omega^p=\omega$, equivalently, $\omega^{p-1}=1$ or $p\equiv 1\pmod 8$, and we have not made a single step.

However, if $\omega=(1+i)/\sqrt 2$, say, the other octic roots of unity are $\omega^7=\omega^{-1}=(1-i)/\sqrt 2$, $\omega^3= (-1+i)/\sqrt 2$ and $\omega^5=-\omega=-(1+i)/\sqrt 2$, so that $\sqrt 2=\omega+\omega^{-1}$. Independely of the previous computations, choose an octic root of unity $\omega$ and set $\alpha=\omega+\omega^{-1}$. This is an element of $\mathbf F_{p^2}$ such that $\alpha^2=\omega^2+\omega^{-2}+2=2$ since $\omega^4=-1$. So the question is whether this element $\alpha$ belongs to $\mathbf F_p$ of not. This can be settled by Fermat's little theorem, and we lead to the conclusion of this complementary law. Indeed $\alpha^p=\omega^p+\omega^{-p}$ is equal to $\alpha$ when $p\equiv \pm1\pmod 4$, and to $-\alpha$ otherwise.

Gauss's lemma and a product formula for the Legendre symbol

Lemma. — (1) Let $S\subset\mathbf F_p^\times$ be a “half-system” modulo $p$, that is, a subset of cardinality $(p-1)/2$ such that every element of $\mathbf F_p^\times$ is of the form $\pm s$ for a unique $s\in S$. For $a\in \mathbf F_p^\times$, one has $\big( \frac ap \big) = (-1) ^m$, where $m=\mathop{\rm Card}( aS \cap (-S))$.
(2) Let $f\colon \mathbf R\to\mathbf C^\times$ be an odd $1$-periodic function. If $p,q$ are distinct odd prime numbers, then
$$\big( \frac qp\big) = \prod_{a=1}^{(p-1)/2}\frac{ f(qa/p) }{f(a/p)}.$$


Proof of (1). For $s\in S$, write $as=\varepsilon(s) s_a$, where $s_a\in S$ and $\varepsilon(s)\in\{\pm1\}$. The map $s\mapsto s_a$ is bijective, so that
$$a^{(p-1)/2} \prod_{s\in S} s = \prod_{s\in S} as = \prod_{s\in S} \varepsilon(s) s_a =\prod_{s\in S} \varepsilon(s) \cdot \prod_{s\in S} s_ a= =\prod_{s\in S} \varepsilon(s) \cdot \prod_{s\in S} s.$$
Simplifying, we get $a^{(p-1)/2}=\prod_{s\in S}\varepsilon(s)$. In this product, there are $m$ factors equal to $-1$, and the other are equal to $1$, so that it equals $(-1)^m$.

Proof of (2). Since $f$ is $1$-periodic, we may define a function $F\colon \mathbf F_p\to \mathbf C^\times$ by setting $F(\alpha)=f(a/p)$ for every lift $a$ of $\alpha$. Then $S=\{1,\dots,(p-1)/2\}$ is a hals-system modulo $p$. It then suffices to compare $\prod_{s\in S} F(qs)$ and $\prod_{s\in S}F(s)$, similarly as in (1).

Application to the complementary law

The relevance of this lemma to the quadratic reciprocity proof is apparent if one considers the case $a=2$. Take $S=\{1,\dots,(p-1)/2\}$. Then, $\varepsilon(s)=1$ if $s\leq (p-1)/4$ and $\varepsilon(s)=-1$ otherwise.
Consequently, $m=(p-1)/4$ if $p\equiv 1\pmod 4$, and $m=(p+1)/4$ if $p\equiv 1\pmod 4$, the discrepancy resulting from the thereshold $(p-1)/4$ for $s$ being an integer or not. If $p\equiv1\pmod4$, this implies $(\frac2p)=1$ if and only if $p\equiv 1\pmod 8$; if $p\equiv 3\pmod3$, this implies $(\frac2p)=1$ if and only if $p\equiv -1\pmod 8$.

The proof of Kronecker — or is it Eisenstein? – and some variations

Eisenstein starts from Gauss's lemma with $f(x)=\sin(2\pi x)$. We get
$$\big( \frac qp\big) = \prod_{a=1}^{(p-1)/2} \frac{\sin(2\pi qa/p)}{\sin(2\pi a/p)}.$$
On the other hand, for every odd integer $q$, there exists a polynomial $U_q$, the Chebyshev polynomial of second kind, such that
$$\sin (qx) = \sin(x) U_q( 4\sin^2(x) ) .$$
The relation
\[\sin((q+2)x)+\sin((q-2)x) = 2\sin(qx)\cos(2x)=2\sin(qx)(1-2\cos^2(x))
=2\sin(qx)(1-2\sin^2(x)) \]
shows that
$$U_{q+2}(T)+U_{q-2}(T) = (2-T)U_q(T).$$
This recurrence relation is initiated with $U_1=1$ and $U_3=3-T$ (I'd even take $U_{-1}=-1$),
so that $U_q$ has integer coefficients, degree $(q-1)/2$ and its leading coefficient is $(-1)^{(q-1)/2}$.
Since $\sin(qx)$ vanishes for $x=k\pi/q\pmod{2\pi}$, the roots of $U_q$ are the $3\sin^2(k\pi/q)$, for $1\leq k\leq (q-1)/2$, and we have the factorization
\[ \sin (qx) = (-1)^{(q-1)/2} \sin(x) \prod_{k=1}^{(q-1)/2} \big( 4\sin^2(x) - 4\sin^2(k\pi/q ) \big)
.\]
Consequently,
\[\big( \frac qp\big) = (-4)^{(q-1)(p-1)/4}
\prod_{a=1}^{(p-1)/2} \prod_{k=1}^{(q-1)/2} \left( \sin ^2(2\pi a/p)- \sin^2(2\pi k/q)\right). \]
By symmetry,
\[ \big( \frac pq\big) = (-4)^{(q-1)(p-1)/4}
\prod_{a=1}^{(q-1)/2} \prod_{k=1}^{(p-1)/2} \left( \sin ^2(2\pi a/q)- \sin^2(2\pi k/p)\right). \]
The big product in the two expressions just differ by the sign of each factor. Consequently,
$$\big( \frac pq\big) = (-1)^{(p-1)(q-1)/4} \big( \frac qp\big),$$
which is the quadratic reciprocity law.

First variation (Kronecker)

The analytic property of the sine function is not really used.
In fact, one can deduce from Gauss's lemma the formula
$$\big(\frac qp\big) = \mathop{\rm sign} \left( \prod_{a=1}^{(p-1)/2} \prod_{k=1}^{(q-1)/2} \big( \frac qp-\frac kq\big)\right) .$$
This implies the quadratic reciprocity law in a similar way.

Second variation (learnt from Jean-François Mestre)

The products appearing in Eisenstein's proof are reminiscent of resultants. In fact,
one has the following formula:
$$\big(\frac qp\big) = \mathop{\rm Res}(U_q,U_p),$$
unless I fucked up the signs.
This equality follows from the analysis above, since the zeroes of $U_q$ are $4\sin^2(k\pi/q)$, and those of $U_p$ are $4\sin^2(a\pi/p)$, but it can also be proved directly.
Indeed, $U_p$ and $U_q$ are polynomials with integer coefficients, so that their resultant is an integer. Moreover, the roots of $U_p$ are of the form $4\sin^2(a\pi/p)$, but is is better to write them $2(1-\cos(2a\pi /p)) = 2-\omega^a-\omega^{-a}$, where $\omega=e^{2i\pi/p}$ is a primitive $p$th root of unity. From this, one can observe than $U_p$ and $U_q$ have no common root, in whatever field of whatever characteristic. Necessarily, their resultant is $\pm1$. To compute the sign, we compute the resultant modulo $p$. Modulo $p$, one has $U_p=(-T)^{(p-1)/2}$, or something like that, and one finds the correct sign.

The proof of Zolotarev — signatures

Lemma (Zolotarev). — For every $a\in\mathbf F_p^\times$, the Legendre symbol $(\frac ap)$ is the signature of the permutation induced by multiplication by $a$ in $\mathbf F_p$.

Many proofs are possible. Let $\varepsilon(a)$ be this signature. One can use the definition of the signature as $(-1)$ to the number of inversions. This definition implies that
$$\varepsilon(a)=\prod_{0\leq x<y\leq p-1} \frac{ay - ax}{y-x} = a^{(p-1)(p-2)/2}=a^{(p-1)/2}$$
since $p-2$ is odd.

On the other hand, the map $\varepsilon\colon\mathbf F_p^\times\to\{\pm1\}$ is a morphism of groups, and the Legendre symbol is the only nontrivial one. If one knows that the group $\mathbf F_p^\times$ is cyclic, it is enough to understand the case of a generator $a$; then multiplication by $a$ has two orbits, $\{0\}$ and $\mathbf F_p^\times$, so that $\varepsilon(a)=(-1)^{p-2}=-1$. This proves that $\varepsilon$ coincides with the Legendre symbol.

One can also derive Zolotarev's lemma from Gauss's lemma.

This lemma admits many generalizations, such as the following one, classically attributed to Frobenius-Zolotarev in French books for future high school teachers (agrégation). The reference I know of it is the 1970 paper Sur une généralisation des symboles de Legendre et de Jacobi by Pierre Cartier.

Lemma. — Let $n$ be a positive integer. For $g\in\mathrm{GL}(n,\mathbf F_p)$ be an invertible matrix, let $\varepsilon(g)$ be the permutation of $\mathbf F_p^n$ induced by $g$. One has $\varepsilon(g)=\big( \frac{\det(g)}p\big)$.

To prove this formula, one can use the fact that $\varepsilon$ is a morphism of groups with values in $\{\pm1\}$. It is trivial on transvections (because transvections have odd order), hence on the $\mathrm{SL}(n,\mathbf F_p)$ they generate, so that it factors through the determinant. If $g$ is diagonal $(a,1,\dots,1)$, one has $\det(g)=a$; on the other hand, the orbit of $(x_1,\dots,x_n)$ is $O(x_1)\times (x_2,\dots,x_n)$, so that it has $m_1p^{n-1}$ orbits, $m_1$ being the number of orbits of multiplication by $a$ on $\mathbf F_p$. Consequently, $\varepsilon(g)=(-1)^{p^n-m_1p^{n-1}}$. Since $p^{n-1}$ is odd, this implies $\varepsilon(g)=(-1)^{p-m_1}=\varepsilon(a)=(\frac ap)$ by Zolotarev's lemma.

It must be noted that only two formulas can hold. Since $\mathrm{SL}(n,\mathbf F_p)$ is the derived subgroup of $\mathrm{GL}(n,\mathbf F_p)$, any morphism to a commutative group factors through the determinant, so that there exists a morphism of groups $\chi\colon \mathbf F_p^\times\to\{\pm1\}$ such that $\varepsilon(g)=\chi(\det(g))$. But there are only two possibilities of $\chi$:
either $\chi$ is the Legendre symbol, or $\chi=1$. So it would have been sufficient to find a matrix $g\in\mathrm{GL}(n,\mathbf F_p)$ such that $\varepsilon(g)=-1$ to conclude. This, however, is not so easy — in the same way that it is not so easy to explicitly produce an element of $\mathbf F_p$ which is not a square.

Another proof of the quadratic reciprocity law

In his Nouvelle démonstration de la loi de réciprocité de Legendre, Zolotarev used this lemma to give another proof of Gauss's quadratic reciprocity law. To prove it, one may consider the permutation $\tau$ of $\mathbf Z/pq\mathbf Z$ that maps $a+pb$ to $b+qa$, for $0\leq a<p$ and $0\leq b<q$. Under the identification of $\mathbf Z/pq\mathbf Z$ with $\mathbf Z/p\mathbf Z\times\mathbf Z/q\mathbf Z$ provided by the Chinese remainder theorem, this permutation is the composite of two permutations, respectively $(x,y)\mapsto (qx+y,y)$ and the inverse of $(x,y)\mapsto (x,py+x)$. Using Zolotarev's lemma, one finds that their signatures are $(\frac qp)$ and $(\frac pq)$ respectively,
so that $\varepsilon(\tau)=(\frac qp )(\frac pq)$. On the other hand, $a+pb<a'+pb'$ if and only if $b<b'$ or $b=b'$ and $a< a'$, so that $\tau(a+pb)=b+qa$ and $\tau(a'+pb')=b'+q'a$ give an inversion if and only if $b<b'$ and $a>a'$ or $b>b'$ and $a<a'$. Taking two pairs $(a,a')$, $(b,b')$ of distinct elements, exactly one of the two arrangements $a+pb, a'+pb'$ or $a+pb',a'+pb$ gives an inversion, so that there are $p(p-1)/2 \cdot q(q-1)/2$ inversions. Since $pq$ is odd, this implies $\varepsilon(\tau)=(-1)^{(p-1)(q-1)/4}$.

Signatures and Galois theory

Galois theory furnishes another relation between Zolotarev's lemma and quadratic reciprocity. Let us indeed consider the finite extension $\mathbf F_q\subset  E$ generated by a primitive $p$th root of unity. This is the decomposition extension of the polynomial $T^p-1$ over $\mathbf F_q$. Its Galois group is generated by the map $a\mapsto a^q$ of $E$ whose action on the $p$th roots of unity is exactly the same as multiplication by $q$ on $\mathbf Z/p\mathbf Z$. By Zolotarev's lemma, the Galois group is contained in the alternate group of the roots if and only if $q$ is a square modulo $p$. On the other hand, there is a well known criterion for the Galois group of a polynomial to be alternate, namely, that the discriminant of the polynomial is a square. The discriminant of $T^p-1$ is classically computed as $(-1)^{p(p-1)/2} p^p  (-1)^{p-1}=(-1)^{(p-1)/2}p \cdot p^{p-1}$ since $p$ is odd. This proves that $(\frac qp)=1$ if and only if $(-1)^{(p-1)/2}p$ is a square in $\mathbf F_q$, in other words,
$$\big( \frac qp\big) = \left( (-1)^{(p-1)/2} p \right)^{(q-1)/2} = (-1)^{(p-1)(q-1)/4} \big( \frac pq\big),$$
which proves once again the quadratic reciprocity law.

Proofs via Gauss sums

Let $\omega$ be a primitive $n$th root of unity in some field $K$. The Gauss sums are the expressions
$$G(\omega)=\sum_{a=1}^{n-1} \omega^{a^2}.$$
If $n=p$ is a prime number, then this can be rewritten as follows, using the fact that the sum of all $p$th roots of unity vanishes:
$$G(\omega)=\sum_{a=0}^{p-1} \big(\frac ap\big) \omega^{a}.$$
The following computation is of the same spirit as the computation done with octic roots of unity (except for the minor fact that $8$ is not an odd prime number).

Lemma. — One has $G(\omega)^2=(-1)^{(p-1)/2} p$.

This starts by a direct computation:
\[ G(\omega)^2=\sum_{a,b\in\mathbf F_p} \big(\frac ap\big) \big(\frac bp\big) \omega^{a+b}
= \sum_{x\in\mathbf F_p} \sum_{a\in\mathbf F_p} \big( \frac{a(x-a)}p\big) \omega^x. \]
Fix $x\in\mathbf F_p$.
If $x=0$, then one has $(\frac{a(x-a)}p)=(\frac{-a^2}p)=(-1)^{(p-1)/2}$ for every $a$, and the coefficient of $\omega^x$ is thus $(-1)^{(p-1)/2}p$.
Assume $x\neq0$. $a\neq 0$, one has $a(x-a)=-a^2(1-x/a)$, hence
$$\big(\frac{a(x-a)}p\big)=(-1)^{(p-1)/2} \big( \frac{1-x/a}p\big)$$
and when $a$ varies, $1-x/a$ takes all values in $\mathbf F_p$ but $1$. Would it take all values, the sum of all $(\frac{1-x/a}p)$ would be zero, because there are as many squares as non squares, and $0$ does not count, so that the sum is $-1$. This gives
\[ G(\omega)^2=(-1)^{(p-1)/2}p - (-1)^{(p-1)/2} \sum_{x\in\mathbf F_p^\times} \omega^x
= (-1)^{(p-1)/2}p \]
because the sum of all non-trivial $p$th roots of unity vanishes.

Proving quadratic reciprocity via finite fields

One way to prove quadratic reciprocity from there is to take for $K$ a finite extension of $\mathbf F_q$, the second prime number. One then has
\[ G(\omega)^q = \sum_{a=0}^{p-1} \big( \frac ap\big)^q \omega^{aq}
= \sum_{b=0}^{p-1} \big(\frac{b/q}p\big) \omega^b , \]
using the change of variables $b=aq$. Since $(\frac{b/q}p\big)=(\frac bp) q^{(p-1)/2}$, we get
$$G(\omega)^q = q^{(p-1)/2} \sum_{b=0}^{p-1} \big(\frac bp\big) \omega^b = \big(\frac qp\big) G(\omega),$$
and
$$G(\omega)^{q-1} = \big( \frac qp\big).$$
Combining this result with the previous lemma, it follows that
$$\left( (-1)^{(p-1)/2} p \right)^{(q-1)/2} = \big( \frac qp \big),$$
which implies quadratic reciprocity after some straightforward manipulations.

Proving quadratic reciprocity via complex numbers

Another way to prove quadratic reciprocity is to choose a specific root of unity in $\mathbf C$, namely $\omega=e^{2i\pi/n}$. If $n=p$ is an odd prime number, then $G(\omega)^2=(-1)^{(p-1)/2}p$ has two roots in $\mathbf C$, and one needs to identify which of them $G(\omega)$ is. Determining the sign of the Gauss sum proved to be a much more difficult problem, and Gauss proved it only later.

Theorem. — One has $G_n=\sqrt n$, $0$, $i\sqrt n$, $(1+i)\sqrt n$ according to $n\equiv 0, 1, 2, 3\pmod 4$.

Writing any integer in $\{1,\dots,pq\}$ as $py+qx$, with $x\in\{1,\dots,p\}$ and $y\in\{1,\dots,q\}$, one can prove that $G_{pq}=G_pG_q (\frac qp)(\frac pq)$. Given the explicit value for $G_p,G_q$ and $G_{pq}$, this implies the quadratic reciprocity law.