Quadratic reciprocity

Let $p$ be a prime, and let $a$ be any integer. Then we can define the Legendre symbol $\genfrac{(}{)}{}{}{a}{p} =\begin{cases} 1 & \text{if } a \text{ is a quadratic residue modulo } p, \\ 0 & \text{if } p \text{ divides } a, \\ -1 & \text{otherwise}.\end{cases}$

We say that $a$ is a quadratic residue modulo $p$ if there exists an integer $n$ so that $n^2\equiv a\pmod p$ .

Equivalently, we can define the function $a \mapsto \genfrac{(}{)}{}{}{a}{p}$ as the unique nonzero multiplicative homomorphism of $\mathbb{F}_p$ into $\mathbb{R}$ .

Quadratic Reciprocity Theorem

There are three parts. Let $p$ and $q$ be distinct odd primes. Then the following hold: $\begin{align*} \genfrac{(}{)}{}{}{-1}{p} &= (-1)^{(p-1)/2} , \\ \genfrac{(}{)}{}{}{2}{p} &= (-1)^{(p^2-1)/8} , \\ \genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} &= (-1)^{(p-1)(q-1)/4} . \end{align*}$ This theorem can help us evaluate Legendre symbols, since the following laws also apply:

If $a\equiv b\pmod{p}$ , then $\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{b}{p}$ .
$\genfrac{(}{)}{}{}{ab}{p}\right) = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$ (Error compiling LaTeX. Unknown error_msg).

There also exist quadratic reciprocity laws in other rings of integers. (I'll put that here later if I remember.)

Proof

Theorem 1. Let $p$ be an odd prime. Then $\genfrac{(}{)}{}{}{-1}{p} = (-1)^{(p-1)/2}$ .

Proof. It suffices to show that $(-1)^{(p-1)/2} = 1$ if and only if $-1$ is a quadratic residue mod $p$ .

Suppose that $-1$ is a quadratic residue mod $p$ . Then $k^2 = -1$ , for some residue $k$ mod $p$ , so $(-1)^{(p-1)/2} = (k^2)^{(p-1)/2} = k^{p-1} = 1 = \genfrac{(}{)}{}{}{-1}{p} ,$ by Fermat's Little Theorem.

On the other hand, suppose that $(-1)^{(p-1)/2} = 1$ . Then $(p-1)/2$ is even, so $(p-1)/4$ is an integer. Since every nonzero residue mod $p$ is a root of the polynomial $(x^{p-1} - 1 = (x^{(p-1)/2} + 1)(x^{(p-1)/2} - 1) ,$ and the $p-1$ nonzero residues cannot all be roots of the polynomial $x^{(p-1)/2} - 1$ , it follows that for some residue $k$ , $\bigl(k^{(p-1)/2}\bigr)^2 = k^{(p-1)/2} = -1 .$ Therefore $-1$ is a quadratic residue mod $p$ , as desired. $\blacksquare$

Now, let $p$ and $q$ be distinct odd primes, and let $K$ be the splitting field of the polynomial $x^q - 1$ over the finite field $\mathbb{F}_p$ . Let $\zeta$ be a primitive $q$ th root of unity in $K$ . We define the Gaussian sum $\tau_q = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^q .$

Lemma. $\tau_q^2 = q (-1)^{(q-1)/2}$

Proof. By definition, we have $\tau_q^2 = \sum_a \sum_b \genfrac{(}{)}{}{}{a}{q} \zeta^a \genfrac{(}{)}{}{}{b}{q} \zeta^b = \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} .$ Letting $c \equiv a^{-1}b \pmod{q}$ , we have $\begin{align*} \sum_{a \neq 0} \sum_b \genfrac{(}{)}{}{}{ab}{q} \zeta^{a+b} &= \sum_{a\neq 0} \sum_c \genfrac{(}{)}{}{}{a^2 c}{q} \zeta^{a+ac} \\ &= \sum_c \sum_{a \neq 0} \genfrac{(}{)}{}{}{c}{q} \bigl( \zeta^{1+c} \bigr)^a \\ &= \sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a . \end{align*}$ Now, $\zeta^{c+1}$ is a root of the polynomial $P(x) = x^q - 1 = (x-1) \sum_{i=0}^{q-1} x^i,$ it follows that for $c\neq -1$ , $\sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = -1,$ while for $c = -1$ , we have $\sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q-1 .$ Therefore $\sum_c \genfrac{(}{)}{}{}{c}{q} \sum_{a \neq 0} \bigl( \zeta^{1+c} \bigr)^a = q \genfrac{(}{)}{}{}{-1}{q} - \sum_{c=0}^{q-1}\genfrac{(}{)}{}{}{c}{q} .$ But since there are $(q-1)/2$ nonsquares and $(q-1)/2$ nonzero square mod $q$ , it follows that $\sum_{c=0}^{q-1} \genfrac{(}{)}{}{}{c}{q} = 0 .$ Therefore $\tau_q^2 = q \genfrac{(}{)}{}{}{-1}{q} = q (-1)^{(q-1)/2} ,$ by Theorem 1.

Theorem 2. $\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4}$ .

Proof. We compute the quantity $\tau_q^p$ in two different ways.

We first note that since $p=0$ in $K$ , $\tau_q^p = \biggl( \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^a \biggr)^p = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q}^p \zeta^{ap} = \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} .$ Since $\genfrac{(}{)}{}{}{p}{q}^2 = 1$ , $\sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{a}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{p}{q} \sum_{a=0}^{q-1} \genfrac{(}{)}{}{}{pa}{q} \zeta^{ap} = \genfrac{(}{)}{}{}{a}{q} \tau_q .$ Thus $\tau_q^p = \genfrac{(}{)}{}{}{p}{q} \tau_q .$

On the other hand, from the lemma,

\[\tau_q^p = (\tau_q^2)^{(p-1)/2} \cdot \tau_q = \bigl[ q (-1)^{(q-1)/2} \bigr]^{(p-1)/2} \tau_q = q^{(p-1)/2} (-1)^{(p-1)(q-1)/4 \tau_q .\] (Error compiling LaTeX. Unknown error_msg)

Since $q^{(p-1)/2} = \genfrac{(}{)}{}{}{q}{p}$ , we then have $\genfrac{(}{)}{}{}{p}{q} \tau_q = \tau_q^p = \genfrac{(}{)}{}{}{q}{p} (-1)^{(p-1)(q-1)/4} \tau_q .$ Since $\tau_q$ is evidently nonzero and $\genfrac{(}{)}{}{}{q}{p}^2 = 1,$ we therefore have $\genfrac{(}{)}{}{}{p}{q} \genfrac{(}{)}{}{}{q}{p} = (-1)^{(p-1)(q-1)/4},$ as desired. $\blacksquare$

References

Helmut Koch, Number Theory: Algebraic Numbers and Functions, American Mathematical Society 2000. ISBN 0-8218-2054-0.

Page

Toolbox

Search

Quadratic reciprocity

Quadratic Reciprocity Theorem

Proof

References