Quadratic Reciprocity

Quadratic reciprocity is usually stated as a remarkable relation between two separate-looking congruence questions. Let $p,q$ be distinct odd primes. The Legendre symbol $\left(\frac{a}{r}\right)$ records whether $a$ is a square modulo $r$ . Thus $\left(\frac{p}{q}\right)$ asks whether the polynomial $X^2-p$ has a root modulo $q$ , while $\left(\frac{q}{p}\right)$ asks the reversed question. Quadratic reciprocity says that these two local questions are almost the same, with one predictable sign correction:

Theorem: Let $p, q$ be two odd primes. We have

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

Here

$\displaystyle \left(\frac{p}{q}\right)= \begin{cases} 1, & \text{if there exists }x\text{ such that }x^2\equiv p\pmod q,\\ -1, & \text{if no such }x\text{ exists}. \end{cases}$

denotes the Legendre symbol which detects whether $p$ is a square modulo $p$ or not. Thus we have a fact relating two local phenomenon. The nature of $p \bmod q$ and $q \bmod p$ . A congruence condition modulo $q$ seems to know something about a congruence condition modulo $p$ .

Quadratic reciprocity is often described as one of the theorems with the largest number of known proofs. Many of those proofs are elementary and combinatorial, but can feel somewhat unmotivated: they establish the identity without fully explaining why these two congruence questions ought to be related at all. The proof discussed here tries to reveal the structure behind the symmetry.

We take the equation $X^2-p$ seriously, reinterpret its roots through a number field, and then use Galois theory to see why the two Legendre symbols must appear together. We are interested in the behaviour of the polynomial $X^2-p$ modulo $q$ . In other words, we are asking whether a certain quadratic equation splits after reducing modulo a prime. This is exactly the kind of question Galois theory is designed to understand. Galois theory studies how roots of polynomials fit together, how fields generated by those roots sit inside larger fields, and how automorphisms act on them. So we should expect the Galois group to enter the picture. The answer is that both Legendre symbols describe the action of the same Frobenius automorphism on one quadratic field.

It is useful to absorb the sign into $p$ . Define $\displaystyle p^*=(-1)^{\frac{p-1}{2}}p.$ Thus $p^{*}=p$ if $p\equiv 1\pmod 4$ , while $p^{*}=-p$ if $p\equiv 3\pmod 4$ . In this notation, quadratic reciprocity becomes

$\displaystyle \left(\frac{q}{p}\right)=\left(\frac{p^*}{q}\right).$

This is the form naturally suggested by the proof. The field that is intrinsically attached to squares modulo $p$ is not always $\mathbb{Q}(\sqrt p)$ ; it is $\mathbb{Q}(\sqrt{p^{*}})$ . The familiar sign in the usual statement of reciprocity is exactly the cost of replacing $p^{*}$ by $p$ .

We begin with arithmetic modulo $p$ . The multiplicative group of nonzero residues modulo $p$ is $\left(\mathbb{Z}/p\mathbb{Z}\right)^*.$ This group is cyclic of order $p-1$ . It is also the Galois group of the $p$ th cyclotomic field $\mathbb{Q}(\zeta_p)$ , where $\zeta_p$ is a primitive $p$ th root of unity. More precisely, an element $a\in\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ corresponds to the automorphism $\sigma_a$ defined by $\sigma_a(\zeta_p)=\zeta_p^a$ . Thus the arithmetic of multiplication modulo $p$ is encoded in the symmetries of the field $\mathbb{Q}(\zeta_p)$ .

Inside $\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ there is a subgroup $S$ of index two: the subgroup of squares. Membership in $S$ is exactly what the Legendre symbol measures. Namely, for $a\not\equiv 0\pmod p$ , we have $a\in S$ precisely when $\left(\frac{a}{p}\right)=1$ . Since $\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ is cyclic, it has exactly one subgroup of each order dividing $p-1$ . In particular, it has a unique subgroup of index two. This simple fact is important: there is only one nontrivial quadratic character on $\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ , namely the Legendre character $a\mapsto \left(\frac{a}{p}\right)$ .

By Galois correspondence, the subgroup $S$ determines a subfield of $\mathbb{Q}(\zeta_p)$ , namely its fixed field $F=\mathbb{Q}(\zeta_p)^S.$ Because $S$ has index two, this field has degree two over $\mathbb{Q}$ . Hence it must be of the form $F=\mathbb{Q}(\sqrt D)$ for some squarefree integer $D$ . The next question is therefore very concrete: which $D$ occurs? To identify it, consider the $p$ th cyclotomic polynomial

$\Phi_p(X)=1+X+X^2+\cdots+X^{p-1}.$

Its discriminant is $\displaystyle {\text{disc}}(\Phi_p)=(-1)^{\frac{p-1}{2}}p^{p-2}.$ The discriminant itself is rational, so it is fixed by every Galois automorphism. The relevant object is instead a square root of the discriminant: the Vandermonde product formed from the roots $\zeta_p,\zeta_p^2,\ldots,\zeta_p^{p-1}$ . Let $\Delta$ denote this product. Then $\Delta^2={\text{disc}}(\Phi_p)$ . An automorphism $\sigma_a$ permutes the roots of $\Phi_p$ by multiplying their exponents by $a$ modulo $p$ . Therefore $\sigma_a(\Delta)$ differs from $\Delta$ only by the sign of this permutation. The resulting sign is a homomorphism from $\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ to ${1,-1}$ . Since there is only one nontrivial such homomorphism, it must be the Legendre symbol. After removing the rational square factor $p^{p-3}$ from $\Delta^2$ , we obtain an element of $\mathbb{Q}(\zeta_p)$ whose square is $p^*$ . Thus we may choose $\sqrt{p^*}$ in $\mathbb{Q}(\zeta_p)$ so that

$\displaystyle \sigma_a(\sqrt{p^{*}})=\left(\frac{a}{p}\right)\sqrt{p^{*}}.$

This formula is the essential structural point. The automorphism corresponding to $a$ fixes $\sqrt{p^*}$ exactly when $a$ is a square modulo $p$ . Therefore the fixed field of the square subgroup is $\displaystyle F=\mathbb{Q}(\sqrt{p^*}).$

We have now constructed a quadratic field inside $\mathbb{Q}(\zeta_p)$ that remembers the square subgroup modulo $p$ . This gives a new way to think about the equation $X^2-p^{*}$ . Although we began with the cyclotomic field, the conclusion is that the square root $\sqrt{p^*}$ can be expressed using $p$ th roots of unity. In other words, the field $\mathbb{Q}(\sqrt{p^*})$ has been placed inside a field whose Galois group is literally the group of nonzero residues modulo $p$ . We really need to think of the above argument as allowing us to write the field in terms of roots of unity and giving a formula for $\sqrt p^*$ in term of roots of unity $\zeta_p.$ (We will give an explicit formula in terms of Gauss sums later)

So far, the prime $q$ has not entered the discussion. It enters through Frobenius. Since $q\neq p$ , the prime $q$ is unramified in $\mathbb{Q}(\zeta_p)$ . Its Frobenius automorphism is $\sigma_q$ , because it acts on roots of unity by raising them to the $q$ th power: $\sigma_q(\zeta_p)=\zeta_p^q$ . This already explains why the residue class of $q$ modulo $p$ appears in the theorem. The automorphism $\sigma_q$ depends only on $q\pmod p$ . Applying the formula above with $a=q$ , we get

$\displaystyle \sigma_q(\sqrt{p^{*}})=\left(\frac{q}{p}\right)\sqrt{p^{*}}.$

Thus $\left(\frac{q}{p}\right)$ tells us whether Frobenius at $q$ fixes $\sqrt{p^{*}}$ or sends it to its negative. Equivalently, it tells us whether Frobenius acts trivially or nontrivially on the quadratic field $\mathbb{Q}(\sqrt{p^{*}})$ .

Now compute the action of the same Frobenius in another way. Let $R$ be the ring of integers of $\mathbb{Q}(\zeta_p)$ , and let $\mathfrak q$ be a prime ideal of $R$ lying above $q$ . Frobenius is characterized by the congruence

$\displaystyle \sigma_q(\alpha)\equiv\alpha^q\pmod{\mathfrak q}$

for every algebraic integer $\alpha$ . Since $\sqrt{p^*}$ is an algebraic integer, we look at how the Frobenius $\sigma_q$ acts on it. We have $\sigma_q(\sqrt p^*)= (\sqrt p^*)^q \mod q$ . Now if $p^*$ is square $\mod q$ , $\sqrt p^*$ is in $\mathbb{F}_{q}$ and we have $(\sqrt p^*)^q =\sqrt p^* \mod q$ , else
$(\sqrt p^*)^q =-\sqrt p^* \mod q$ .

Thus we have

$\displaystyle \sigma_q(\sqrt p^*)= (\sqrt p^*)^q =\left(\frac{p^*}{q}\right) \sqrt p^* \mod q .$

This has a clear interpretation. The polynomial $X^2-p^*$ splits modulo $q$ exactly when $\left(\frac{p^*}{q}\right)=1$ . In that case its two roots are already defined over $\mathbb{F}_q$ , and Frobenius fixes each root. If it does not split, the roots lie only over the quadratic extension of $\mathbb{F}_q$ , and Frobenius interchanges them. Thus Frobenius acts by the sign $\left(\frac{p^*}{q}\right)$

But this is the same Frobenius action that was already computed as $\left(\frac{q}{p}\right)$ . Since $\sqrt{p^*}$ is nonzero modulo $\mathfrak q$ , the two signs must agree:

$\displaystyle \left(\frac{q}{p}\right)=\left(\frac{p^*}{q}\right).$

This is quadratic reciprocity in its most conceptual form. Expanding $p^*=(-1)^{(p-1)/2}p$ and using $\left(\frac{-1}{q}\right)=(-1)^{(q-1)/2}$ immediately recovers the standard formula. The central insight is that the two Legendre symbols arise from one object. The symbol $\left(\frac{q}{p}\right)$ asks whether $q$ belongs to the square subgroup of $\left(\mathbb{Z}/p\mathbb{Z}\right)^*$ . Galois correspondence turns this subgroup into the field $\mathbb{Q}(\sqrt{p^*})$ . Frobenius at $q$ acts on this field in a way determined by $q\pmod p$ , but reduction modulo $q$ shows that the same action is determined by whether $p^{*}$ is a square modulo $q$ . Reciprocity is the equality of these two descriptions.

There is also a very explicit way to write $\sqrt{p^*}$ in terms of roots of unity. Define the quadratic Gauss sum

$\displaystyle g=\sum_{k\bmod p}\left(\frac{k}{p}\right)\zeta_p^k.$

For $a\not\equiv 0\pmod p$ , let $g_a=\sum_{k\bmod p}\left(\frac{k}{p}\right)\zeta_p^{ak}$ . Changing variables shows that $g_a=\left(\frac{a}{p}\right)g$ . Thus the Gauss sum transforms under Galois automorphisms exactly as $\sqrt{p^*}$ does: square automorphisms fix it, while nonsquare automorphisms negate it.

To compute $g^2$ , consider $\sum_{0<a<p}g_ag_{-a}$ . Since $g_a=\left(\frac{a}{p}\right)g$ , every summand is $\left(\frac{-1}{p}\right)g^2$ , so the sum equals $(p-1)\left(\frac{-1}{p}\right)g^2$ . On the other hand, expanding the Gauss sums and summing over $a$ uses the elementary orthogonality relation for additive characters: the sum $\sum_{a\neq 0}\zeta_p^{a(x-y)}$ equals $p-1$ when $x=y$ and $-1$ otherwise. The result is

$\displaystyle \sum_{0<a<p}g_ag_{-a}=p(p-1).$

Comparing the two evaluations gives

$\displaystyle g^2=\left(\frac{-1}{p}\right)p=p^*.$

Therefore we obtain the explicit formula

$\displaystyle \sqrt{p^*}=\sum_{k\bmod p}\left(\frac{k}{p}\right)\zeta_p^k,$

up to the choice of one of the two square roots. The calculation should be viewed as finite Fourier analysis. The functions $k\mapsto\zeta_p^{ak}$ are additive characters of $\mathbb{Z}/p\mathbb{Z}$ , while $k\mapsto\left(\frac{k}{p}\right)$ is a multiplicative character. The Gauss sum measures the interaction between these two kinds of symmetry. The argument above determines $g^2$ , which is all that quadratic reciprocity requires. Determining the precise complex sign of $g$ requires additional work: one must use the analytic structure of $\mathbb{C}$ and a chosen embedding in order to distinguish the two square roots. That is the classical problem of determining the sign of the Gauss sum.

To summarize: We had a way of writing the quantity $\sqrt{p^{*}}$ in terms of the roots of unity $\zeta_p$ . Next, Frobenius allows us to relate the splitting of $X^2-p^{*} \mod q$ to $\sqrt{p^{*}}^{q} \mod q$ . But the fact that $\sqrt{p^{*}}$ has an expression in terms of $\zeta_p$ means that $\sqrt{p^{*}}^{q} \mod q$ is determined by $q \mod p$ . The fact that it is in the fixed field of squares shows that it depends only on $\left(\frac{q}{p}\right)$ . All we needed to do was use the subgroup $S$ of squares of $\left(\mathbb{Z}/p\mathbb{Z}\right)^{*}$ to check if $q$ belongs to it. This obviously captures $\left(\frac{q}{p}\right)$ . To relate to the other side $\left(\frac{p^{*}}{q}\right)$ , we use Galois correspondence to find out the field corresponding to $S$ and consider the action of $\sigma_q$ on the field.