Statement of the Quadratic Reciprocity Law

In this section we state the quadratic reciprocity law.

Definition 4.1 (Quadratic Residue)   Fix a prime $p$ . An integer $a$ not divisible by $p$ is a quadratic residue modulo $p$ if $a$ is a square modulo $p$ ; otherwise, $a$ is a quadratic nonresidue.

For example, the squares modulo $5$ are

$$1^2 = 1, \quad 2^2 = 4, \quad 3^2 = 4, \quad 4^2 = 1, \qquad\pmod{5}$$

so $1$ and $4$ are both quadratic residues and $2$ and $3$ are quadratic nonresidues.

The quadratic reciprocity theorem is the deepest theorem that we will prove in this book. It connects the question of whether or not $a$ is a quadratic residue modulo $p$ to the question of whether $p$ is a quadratic residue modulo each of the prime divisors of $a$ . To express it precisely, we introduce some new notation.

Definition 4.1 (Legendre Symbol)   Let $p$ be an odd prime and let $a$ be an integer coprime to $p$ . Set

$$\left(\frac{a}{p}\right) = \begin{cases} +1 & \text{if $a$ ... ... quadratic residue, and}\\ -1 & \text{otherwise}. \end{cases}$$

We call this symbol the Legendre Symbol.

For example, we have

$$\left(\frac{1}{5}\right) = 1,\quad \left(\frac{2}{5}\right) = -1,\quad \left(\frac{3}{5}\right) = -1,\quad \left(\frac{4}{5}\right) = 1.$$

This notation is well entrenched in the literature even though it is also the notation for ``$a$ divided by $p$ ''; be careful not to confuse the two.

SAGE Example 4.1   Use the command legendre_symbol to compute the Legendre symbol in SAGE.

sage: legendre_symbol(2,3)
-1
sage: legendre_symbol(1,3)
1
sage: legendre_symbol(3,5)
-1
sage: legendre_symbol(Mod(3,5), 5)
-1

Since $\left(\frac{a}{p}\right)$ only depends on $a\pmod{p}$ , it makes sense to define $\left(\frac{a}{p}\right)$ for $a\in\mathbb{Z}/p\mathbb{Z}{}$ to be $\left(\frac{\tilde{a}}{p}\right)$ for any lift $\tilde{a}$ of $a$ to  $\mathbb {Z}$ .

Recall (see Definition 3.3.6) that a group homomorphism $\varphi :G\to H$ is a map such that for every $a,b\in G$ we have $\varphi (ab) = \varphi (a) \varphi (b)$ . Moreover, we say that $\varphi$ is surjective if for every $c\in H$ there is an $a\in G$ with $\varphi (a) = c$ . The next lemma explains how the quadratic residue symbol defines a surjective group homomorphism.

Lemma 4.1   The map $\psi:(\mathbb{Z}/p\mathbb{Z}{})^*\to \{\pm 1\}$ given by $\psi(a) = \left(\frac{a}{p}\right)$ is a surjective group homomorphism.

Proof. By Theorem 2.5.8, primitive roots exist, so there is $g\in(\mathbb{Z}/p\mathbb{Z}{})^*$ such that the elements of $(\mathbb{Z}/p\mathbb{Z}{})^*$ are

$$g, g^2, \ldots, g^{(p-1)/2}, g^{(p+1)/2}, \ldots, g^{p-1}=1.$$

Since $p-1$ is even, the squares of elements of $(\mathbb{Z}/p\mathbb{Z}{})^*$ are

$$g^2, g^4, \ldots, g^{(p-1)/2 \cdot 2}=1, g^{p+1}=g^2,\ldots, g^{2(p-1)}.$$

Note that the powers of $g$ starting with $g^{p+1}=g^2$ all appeared earlier on the list. Thus the perfect squares in $(\mathbb{Z}/p\mathbb{Z}{})^*$ are exactly the powers $g^n$ with $n=2,4,\ldots,p-1$ , even, and the nonsquares the powers $g^n$ with $n=1,3,\ldots,p-2$ , odd. It follows that $\psi$ is a homomorphism since an odd plus an odd is even, the sum of two evens is even, and and odd plus an even is odd. Moreover, since $g$ is not a square, $\psi(g)=-1$ , so $\psi$ is surjective.

$\qedsymbol$

Remark 4.1   We rephrase the above proof in the language of group theory. The group $G=(\mathbb{Z}/p\mathbb{Z}{})^*$ of order $p-1$ is a cyclic group. Since $p$ is odd, $p-1$ is even, so the subgroup $H$ of squares of elements of $G$ has index $2$ in $G$ . (See Exercise 4.2 for why $H$ is a subgroup.) Since $\left(\frac{a}{p}\right)=1$ if and only if $a\in H$ , we see that $\psi$ is the composition $G\to G/H\cong \{\pm 1\}$ , where we identify the nontrivial element of $G/H$ with $-1$ .

Remark 4.1   We can alternatively prove that $\psi$ is surjective without using that $(\mathbb{Z}/p\mathbb{Z}{})^*$ is cyclic, as follows. If $a\in (\mathbb{Z}/p\mathbb{Z}{})^*$ is a square, say $a\equiv b^2\pmod{p}$ , then $a^{(p-1)/2} = b^{p-1}\equiv 1\pmod{p}$ , so $a$ is a root of $f=x^{(p-1)/2}-1$ . By Proposition 2.5.3, the polynomial $f$ has at most $(p-1)/2$ roots. Thus there must be an $a\in (\mathbb{Z}/p\mathbb{Z}{})^*$ that is not a root of $f$ , and for that $a$ , we have $\psi(a)=\left(\frac{a}{p}\right)=-1$ , and trivially $\psi(1)=1$ , so the map $\psi$ is surjective. Note that this argument does not prove that $\psi$ is a homomorphism.

The symbol $\left(\frac{a}{p}\right)$ only depends on the residue class of $a$ modulo $p$ , so making a table of values $\left(\frac{a}{5}\right)$ for many values of $a$ would be easy. Would it be easy to make a table of $\left(\frac{5}{p}\right)$ for many $p$ ? Perhaps, since there appears to be a simple pattern in Table 4.1.

Table 4.1: When is $5$ a square modulo $p$ ?

$p$	$\left(\frac{5}{p}\right)$	$p$ mod 5
7	$-1$	2
11	$1$	1
13	$-1$	3
17	$-1$	2
19	$1$	4
23	$-1$	3

        

$p$	$\left(\frac{5}{p}\right)$	$p$ mod 5
29	$1$	4
31	$1$	1
37	$-1$	2
41	$1$	1
43	$-1$	3
47	$-1$	2

It seems that $\left(\frac{5}{p}\right)$ depends only on the congruence class of $p$ modulo $5$ . More precisely, $\left(\frac{5}{p}\right)=1$ if and only if $p\equiv 1,4\pmod{5}$ , i.e., $\left(\frac{5}{p}\right)=1$ if and only if $p$ is a square modulo $5$ .

Based on similar observations, in the 18th century various mathematicians found a conjectural explanation for the mystery suggested by Table 4.1. Finally, on April 8, 1796, at the age of 19, Gauss proved the following theorem.

Theorem 4.1 (Gauss's Quadratic Reciprocity Law)   Suppose $p$ and $q$ are distinct odd primes. Then

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

Also

$$\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$$   and$$\qquad \left(\frac{2}{p}\right) = \begin{cases}\hfill1 & \text{\r... ...\equiv \pm 1\pmod{8}\\ -1 & \text{\rm if } p \equiv \pm 3\pmod{8}. \end{cases}$$

We will give two proofs of Gauss's formula relating $\left(\frac{p}{q}\right)$ to $\left(\frac{q}{p}\right)$ . The first elementary proof is in Section 4.3, and the second more algebraic proof is in Section 4.4.

In our example Gauss's theorem implies that

$$\left(\frac{5}{p}\right) = (-1)^{2\cdot \frac{p-1}{2}} \left(\fra... ...{ if }p\equiv 1, 4\pmod{5}\\ -1 & \text{ if }p\equiv 2, 3\pmod{5}. \end{cases}$$

As an application, the following example illustrates how to answer questions like ``is $a$ a square modulo $b$ '' using Theorem 4.1.7.

Example 4.1   Is $69$ a square modulo the prime $389$ ? We have

$$\left(\frac{69}{389}\right) = \left(\frac{3\cdot 23}{389}\right) =\left(\frac{3}{389}\right)\cdot \left(\frac{23}{389}\right) = (-1)\cdot(-1)= 1.$$

Here

$$\left(\frac{3}{389}\right) = \left(\frac{389}{3}\right) = \left(\frac{2}{3}\right)=-1,$$

and

$$\left(\frac{23}{389}\right) = \left(\frac{389}{23}\right) = \left(\frac{21}{23}\right)= \left(\frac{-2}{23}\right)$$

$$= \left(\frac{-1}{23}\right)\left(\frac{2}{23}\right) =(-1)^{\frac{23-1}{2}}\cdot 1 = -1.$$

Thus $69$ is a square modulo $389$ .

SAGE Example 4.1   We could also do this computation in SAGE as follows:

sage: legendre_symbol(69,389)
1

Though we know that $69$ is a square modulo $389$ , we don't know an explicit $x$ such that $x^2\equiv 69\pmod{389}$ ! This is reminiscent of how we could prove using Theorem 2.1.19 that certain numbers are composite without knowing a factorization.

Remark 4.1   The Jacobi symbol is an extension of the Legendre symbol to composite moduli. For more details, see Exercise 4.9.