Quadratic Reciprocity

Quadratic reciprocity is one of many deep facts of arithmetic relating different local properties (modulo primes). In this post I try to explain it in terms I understand.

I always wanted to write about it, but have been postponing.

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 $\left( \frac{p}{q}\right)$ 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 \mod q$ and $q \mod p$ .
There are several proofs of the result. This is supposed to be the result with largest number of known proofs!,

But many of the proofs are combinatorial and can look unmotivated. Here I discuss a proof which shows the depth of the relation by really asking what the equation $X^2-p$ means.

We are looking for the behaviour of the polynomial $X^2 -p$ $\mod q$ . So we should expect some Galois theory here to understand the polynomial, structure of the field extensions and so Galois group come into the picture.

Since we are working mod $p$ , we are concerned with the group $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$ which is the Galois group of $\mathbb{Q}(\zeta_p)$ . It has a subgroup $S$ of index 2 which corresponds to the squares of $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$ .
By Galois correspondence , it corresponds to an extension of degree $2$ over $\mathbb{Q}$ . Thus $F=\mathbb{Q}(\sqrt D)$ for some $D$ .

We can actually determine $D$ explicitly in terms of $p$ . The only subgroup of $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$ of index two is the the subgroup $S$ of squares. To see this note that $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$ . is cyclic of order $p-1$ and has exactly one subgroup of order $d$ for all $d|p-1$ .

Hence there is only one required quadratic extension of $\mathbb{Q}(\zeta_p)$ . We will now explicitly determine a $D$ such that the field required is $\mathbb{Q}(\sqrt D)$ .

We see that the discriminant $d$ of the polynomial $f(x)= 1+x+x^2+...x^{(p-1)}$ is $d(p)=(-1)^{(p-1)/2} p^{(p-2)}$ . It can be easily checked that that it $\sigma (d)=-d$ where $\sigma$ is the automorphism corresponding to $\zeta \to \zeta^2$ .
Therefore $d$ is one such required candidate. Let us take $D=(-1)^{\frac{p-1}{2}} p:=p^*$ be the squarefree part of $d$ . Therefore $F=Q(\sqrt p^*)$ .

So far we found a quadratic field $F=Q(\sqrt p^*)$ contained in $\mathbb{Q}(\zeta_p)$ which is the fixed field for squares in the Galois group $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$ . This you should think of as giving a way to look at the equation $X^2 -p^{*}$ . Although we started with the cyclotomic field and obtained this as subfield, 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 $q$ didn’t come into the picture! It enters now.

Now let us see what the action of the Frobenius $\sigma_q$ is. We look at this because this is how the element $q \mod p$ interacts with the present structure.

We use the fact that $\sigma_q$ ,the Frobenius at $q$ satisfies $\sigma_q(\alpha)=\alpha^q \mod (qR)$ where $R$ is the ring of integers of $\mathbb{Q}(\zeta _p)$ .

$\sqrt p^{*}$ is an algebraic integer. So 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 $\sigma_q(\sqrt p^*)= (\sqrt p^*)^q =\left(\frac{p^*}{q}\right) \sqrt p^* \mod q .$

We will now show that $\sigma_q(\sqrt p^*) =\left (\frac{q}{p} \right) \sqrt p^*$ and by the above we get the desired equality $\left(\frac{q}{p}\right)=\left(\frac{p^*}{q}\right)$ .

This is easy to see because $\sigma_a(\sqrt p^*)=\chi(a)\sqrt p^*$ where $\chi(a)$ takes the values 1 or -1 and $\chi: \left(\mathbb Z/p\mathbb{Z}\right)^{*} \to \{-1,1\}$ is a homomorphism. Thus $\chi(a)=(a/q)$ as there is only one subgroup of index 2 in $\left(\mathbb Z/p\mathbb{Z}\right)^{*}$

Thus we are done! We had a way to write the quantity $\sqrt{p^{*}}$ in terms of the the roots of unity $\zeta_p$ . Next Frobenius allows us to study 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 the $\sqrt{p^{*}}^{q} \mod q$ is determined by $q \mod p$ . The fact that it is in the fixed field of squares show that it just depends on $\left(\frac{q}{p}\right)$

An explicit expression for $\sqrt p^*$ in terms of roots of unity is the following Gauss sum computation.

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

We will show $g^2=p^*$ by computing $\sum_{0<a<p} g_a g_{-a}$ in two different ways, where

$\displaystyle g_a =\sum_{k \mod p} \left(\frac{k}{p}\right) \zeta_p^{ak}$

We have that $g_a= \left(\frac{a}{p}\right) g_1$ . So we have $g_a g_{-a}= (-1/p)g^2$ . So we see that

$\displaystyle \sum_{0<a<p} g_a g_{-a} =(p-1) (-1/p)g^2$

But by using expansion of the Gauss sums, taking the products and summing over $a$ , we have

$\displaystyle \sum g_a g_-a = \sum\sum \left(x/p\right) \left(y/p\right) \delta(x,y) p = (p-1)p$ .

Thus we proved $g^2 = \left(-1/p\right) p =p^{*} .$

The above computations should be looked as Fourier analysis over the finite abelian group $\left(\mathbb {Z}/p\mathbb{Z}\right)^*$ and $\mathbb{Z}/p\mathbb{Z}$ .

We would need much more work to determine the “Sign of Gauss Sum”. Here we need to use the analytic structure of $\mathbb{C}$ to differentiate between the square-roots.

To summarize 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.