7 The reciprocity law

7.1 The statement

In the previous section the prime $p$ was fixed, and we are asking “which $a$ are quadratic residues mod $p$”? But we can also do something else: we can fix an integer $a,$ and ask “for which (odd) primes $p \nmid a$ is $a$ a quadratic residue mod $p$?” For instance, with $a = 5,$ we see the following:

Residue: $\{11, 19, 29, 31, 41, 59, 61, 71, \dots\}$

Non-residue: $\{3, 7, 13, 17, 23, 37, 43, 47, \dots\}$

Notice the last digits! Amazingly, the answer seems to depend only on $p$ mod 5 – which is strange, since the question is about $5 \bmod p,$ not $p \bmod 5,$ and these are totally different things.

If you try other values of $a,$ the answer doesn’t always depend on $p \bmod a,$ but it’s not far off – it suffices to know $p \bmod 4a.$ This is the first hint at the following beautiful and important theorem:

Theorem 7.1 • Gauss’ law of quadratic reciprocity

If $p, q$ are two distinct odd primes, then \[\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\tfrac{(p-1)}{2} \cdot \tfrac{(q-1)}{2}} = \begin{cases} \phantom{-}1 & \text{if at least one of $p, q$ is $1 \bmod 4$} \\ -1 & \text{if both are $3 \bmod 4$}. \end{cases}\]

Along with Gauss’ law there are two related theorems (the “supplements to quadratic reciprocity”): one for $\left(\frac{-1}{p}\right)$ (which we have already proved as Proposition 6.6 above), and another for $\left(\frac{2}{p}\right)$ (which we will prove below). These say that for any odd prime $p$ we have \[\left(\frac{-1}{p}\right) = (-1)^{\tfrac{(p-1)}{2}} = \begin{cases} \phantom{-}1 & \text{if $p = 1 \bmod 4$}\\ -1 & \text{if $p = 3 \bmod 4$} \end{cases}\] and \[\left(\frac{2}{p}\right) = (-1)^{\tfrac{(p^2-1)}{8}} = \begin{cases} \phantom{-}1 & \text{if $p = \pm 1 \bmod 8$}\\ -1 & \text{if $p =\pm 3 \bmod 8$}. \end{cases}\]

The quadratic reciprocity law has many different proofs; Gauss himself published six different proofs in his lifetime, and hundreds more have been found since. However, none of them are particularly easy – whichever way you approach it, you have to do some genuine work. We’ll give a proof shortly, which is quite close to one of Gauss’ original arguments. First, we note that this does explain the observations above:

Corollary 7.2

Let $a \in \mathbb{Z}$ be non-zero, and $p,$ $q$ odd primes, not dividing $a,$ such that $p = q \bmod 4|a|.$ Then $\left(\frac{a}{p}\right) = \left(\frac{a}{q}\right).$

Proof. Considering the prime factorisation of $|a|$ and using the multiplicativity of the Legendre symbol, we may suppose that we are in one of three cases: $a = -1,$ $a = 2,$ or $a$ is an odd prime. The first two cases are OK by the two supplementary laws, so we suppose we are in the third case.

Since $p = q \bmod 4|a|,$ either $p = q = 1 \bmod 4$ or $p = q = 3 \bmod 4.$ If $p = q = 1 \bmod 4,$ or if $a = 1 \bmod 4,$ then we have \[\left(\frac{a}{p}\right) = \left(\frac{p}{a}\right) = \left(\frac{q}{a}\right) = \left(\frac{a}{q}\right).\] If $a, p, q$ are all $3 \bmod 4,$ then we have similarly \[\left(\frac{a}{p}\right) = -\left(\frac{p}{a}\right) = -\left(\frac{q}{a}\right) = \left(\frac{a}{q}\right).\]

7.2 Gauss sums

We’ll first give a fairly “hands-on” proof of quadratic reciprocity in a special case: let $p, q$ be odd primes, and assume that $p = 1 \bmod q.$

Then there exists an element $\zeta \in \mathbb{F}_p^\times$ of exact order $q.$ So we may consider the “Gauss sum” \[G(\zeta) = \sum_{a \in \mathbb{F}_q^\times} \left(\frac{a}{q}\right) \zeta^a\qquad \in \mathbb{F}_p.\] (Since $\zeta^q = 1,$ the power $\zeta^n$ only depends on $a \bmod q,$ so it makes sense to consider $\zeta^a$ for $a \in \mathbb{F}_q.$)

Exercise 7.3

Does $G(\zeta)$ depend on which order $q$ element we choose?

Proposition 7.4

We have $G(\zeta) ^ 2 = \left(\frac{-1}{q}\right) q.$

Proof. This follows by an explicit manipulation of sums. By definition we have \[G(\zeta)^2 = \sum_{a, b \in \mathbb{F}_q^\times} \left(\frac{a}{q}\right)\left(\frac{b}{q}\right) \zeta^{a + b}.\] Clearly, for any $a, b \in \mathbb{F}_q^\times$ there’s a unique $k \in \mathbb{F}_q^\times$ such that $b = k a,$ so we can write \[G(\zeta)^2 = \sum_{a, k \in \mathbb{F}_q^\times} \left(\frac{a}{q}\right)\left(\frac{ka}{q}\right) \zeta^{a(1 + k)} = \sum_{a, k \in \mathbb{F}_q^\times} \left(\frac{k}{p}\right) \zeta^{a(1 + k)}.\]

We’re going to group this into a sum over $a$ on the inside, and a sum over $k$ on the outside: \[G(\zeta)^2 = \sum_{k \in \mathbb{F}_q^\times}\left(\frac{k}{q}\right) \left(\sum_{a \in \mathbb{F}_q^\times} \zeta^{a(1 + k)}\right).\] So, what is $\left(\sum_{a \in \mathbb{F}_q^\times} \zeta^{a(1 + k)}\right)$? If $k = -1,$ then it is $1 + \dots + 1$ (with $q - 1$ terms), so just $q - 1.$ On the other hand, if $k \ne -1,$ then $\xi = \zeta^{k + 1}$ also has exact order $q,$ so using the formula for the sum of a geometric progression, \[\begin{aligned} \xi + \dots + \xi^{q-1} &= \frac{\xi^q - \xi}{\xi - 1}\\ &= \frac{1 - \xi}{\xi - 1} = -1. \end{aligned}\] Hence \[G(\zeta)^2 = (q - 1)\left(\frac{-1}{q}\right) - \sum_{\substack{k \in \mathbb{F}_q^\times \\ k \ne -1}} \left(\frac{k}{q}\right) = q\left(\frac{-1}{q}\right) - \sum_{k \in \mathbb{F}_q^\times} \left(\frac{k}{q}\right).\] To complete the proof we have to show that the sum $S = \sum_{k \in \mathbb{F}_q^\times} \left(\frac{k}{q}\right)$ is zero. But if we take any $u \in \mathbb{F}_q^\times$ which isn’t a square, and substitute $j = u k$ in the sum, then the sum gets multiplied by $\left(\frac{u}{q}\right) = -1.$ This shows that $S = -S,$ so $S = 0$ as required.

Corollary 7.5

If $p = 1 \bmod q,$ then $q$ is a square mod $p,$ unless $p = q = 3 \bmod 4,$ in which case $q$ is not a square mod $p.$

Proof. If $q = 1 \bmod 4,$ then $\left(\frac{-1}{q}\right) = 1$ and $G(\zeta)$ is a square root of $q \bmod p.$ If $q = 3 \bmod 4,$ then $G(\zeta)$ is a square root of $-q \bmod p,$ so $q$ is a square $\bmod p$ iff $-1$ is.

7.3 Enlarging the field

The above Gauss-sums proof for $p = 1 \bmod q$ is very tidy, but it leaves many cases unsolved: if $p$ is a square mod $q,$ but $p \ne 1 \bmod q,$ we can’t find an element of exact order $q$ in $\mathbb{F}_p^\times$ with which to form a Gauss sum. The solution is to work in field extensions of $\mathbb{Z}/p$: fields $\mathbb{K}$ containing $\mathbb{Z}/p$ as a subfield.

Let’s first look at the case of $p, q$ odd primes (with $p \ne q$). We’ll use the following theorem, which we’ll prove in a moment:

Theorem 7.6

There exists a field $\mathbb{K},$ and an element $\zeta \in \mathbb{K}^\times,$ such that

$\mathbb{K}$ contains $\mathbb{F}_p$ as a subfield;
$\zeta$ has exact order $q$ in $\mathbb{K}^\times$ (that is, $\zeta^q = 1$ but $\zeta \ne 1$).

Then we can run the same machine as before, defining \[G(\zeta) = \sum_{a \in \mathbb{F}_q^\times} \left(\frac{a}{q}\right) \zeta^a\qquad \in \quad \mathbb{K},\] and the same proof as before shows that $G(\zeta)^2 = \left(\frac{-1}{q}\right) q.$ But we want to know if $q$ (or $\left(\frac{-1}{q}\right) q$) is the square of something in $\mathbb{F}_p$, not just in the larger field $\mathbb{K}.$ So, we need to ask: when does $G(\zeta)$ lie in the subfield $\mathbb{F}_p$ of $\mathbb{K}$?

The trick is to compute $G(\zeta)^p.$ Since $p = 0$ in $\mathbb{K},$ we have $(x + y)^p = x^p + y^p$ for any $x, y \in \mathbb{K}$; hence \[G(\zeta)^p = \sum_{a \bmod q} \left(\frac{a}{q}\right) \zeta^{p a} = \sum_{b \bmod q} \left(\frac{p^{-1}b}{q}\right) \zeta^b,\] since multiplying by $p$ is a bijection on $\mathbb{F}_q^\times.$ Using the multiplicativity of the Legendre symbol this is just \[\left(\frac{p^{-1}}{q}\right) G(\zeta) = \left(\frac{p}{q}\right) G(\zeta).\]

If $\left(\frac{p}{q}\right) = 1,$ then we’ve shown that $G(\zeta)$ is a root of $X^p - X$ in $\mathbb{K}.$ However, all the elements of $\mathbb{F}_p$ are roots of $X^p - X$ (Fermat’s little theorem); and since $\mathbb{K}$ is a field, a polynomial of degree $p$ can’t have more than $p$ roots in $\mathbb{K}.$ Hence $G(\zeta)$ must actually be in $\mathbb{F}_p,$ and we’ve shown that $\left(\frac{-1}{q}\right) q$ is a square mod $p.$

Conversely, if $\left(\frac{p}{q}\right) \ne 1,$ then $G(\zeta)$ is not a root of $X^p - X,$ so $G(\zeta)$ cannot be in $\mathbb{F}_p.$ So $G(\zeta),$ and likewise $-G(\zeta),$ are square roots of $\left(\frac{-1}{q}\right) q$ in $\mathbb{K}$ that aren’t in $\mathbb{F}_p.$ Since $\left(\frac{-1}{q}\right) q$ can’t have more than two square roots in $\mathbb{K},$ it follows that $\left(\frac{-1}{q}\right) q$ has no square root in $\mathbb{F}_p.$

Thus $\left(\frac{-1}{q}\right) q$ is a square mod $p$ iff $p$ is a square mod $q,$ which is equivalent to Quadratic Reciprocity.

7.4 The supplementary law for 2

We can handle the supplementary law for $\left(\frac{2}{p}\right)$ similarly, with a little more notation. For $a \in (\mathbb{Z}/ 8)^\times,$ define \[\psi(a) = \begin{cases} 1 & \text{if $a = \pm 1 \bmod 8$}\\ -1 & \text{if $a = \pm 3 \bmod 8$}.\end{cases}\] Then one has $\psi(ab) = \psi(a) \psi(b)$ (an easy check).

If $p$ is an odd prime, then we can find a field extension $\mathbb{K}$ of $\mathbb{F}_p$ containing an element $\zeta \in \mathbb{K}$ of order exactly 8 (so $\zeta^4 = -1$). We define \[G(\zeta) = \sum_{a \in (\mathbb{Z}/ 8)^\times} \psi(a) \zeta^a = \zeta - \zeta^3 - \zeta^5 + \zeta^7 \qquad \in \quad \mathbb{K}.\] A calculation now shows that $G(\zeta)^2 = 8,$ and $G(\zeta)^p = \psi(p) G(\zeta).$ So if $\psi(p) = 1,$ then $\tfrac{1}{2}G(\zeta) \in \mathbb{Z}/p$ is a square root of 2; conversely, if $\psi(p) = -1,$ then the square roots of 2 in $\mathbb{K}$ do not lie in $\mathbb{Z}/p,$ so 2 cannot be a square in $\mathbb{Z}/p.$ So we deduce \[\left(\frac{2}{p}\right) = \psi(p),\] which is the supplementary law.

7.5 Finding the field

Now we finish the argument by explaining why the field $\mathbb{K}$ exists. For $q$ an odd prime, consider the polynomial (a cyclotomic polynomial) \[\Phi_q(X) = \frac{X^q - 1}{X - 1} = 1 + X + X^2 + \dots + X^{q-1} \in \mathbb{Z}[X].\] If we reduce $\Phi_q \bmod p,$ for $p \ne q$ another odd prime, we get a polynomial $\bar{\Phi}_q(X) \in \mathbb{F}_p[X].$ This will factor into a product of powers⁸ of irreducibles (since polynomials over any field are a Euclidean domain). Let $F$ be any such irreducible factor.

Then $\mathbb{K}= \mathbb{F}_p[X] / F(X)$ is a field (because $F$ is irreducible, see Algebra chapter 10); it clearly contains $\mathbb{F}_p$; and the element $\zeta = X \bmod F(X) \in \mathbb{K}$ satisfies $\Phi_q(X) = 0.$ Hence $\zeta^q = 1,$ but $\zeta \ne 1$ (since $\Phi_q(1) = q \bmod p \ne 0$). Thus $\zeta$ has exact order $q$ in $\mathbb{K}^\times.$ as required.

Exercise 7.7

By considering the mod $p$ reduction of $\frac{X^8 - 1}{X^4 - 1} = X^4 + 1,$ show that for any odd prime $p$ there exists a field extension $\mathbb{K}$ of $\mathbb{F}_p,$ and an element $\zeta \in \mathbb{K}^\times,$ such that $\zeta$ has order exactly 8.

7 The reciprocity law

7.1 The statement

7.2 Gauss sums

7.3 Enlarging the field

7.4 The supplementary law for 2

7.5 Finding the field

Home

Chapters

Contents

PDFs

✕