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 nontrivial multiplicative homomorphism of $\mathbb{F}_p^\times$ into $\mathbb{R}^\times$, extended by $0 \mapsto 0$.

There are three parts. Let $p$ and $q$ be distinct odd primes. Then the following hold:

• $\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} .$

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} = \genfrac{(}{)}{}{}{a}{p} \genfrac{(}{)}{}{}{b}{p}$.

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 .$$ 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$

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

Proof. Let $K$ be the splitting field of the polynomial $x^8-1$ over $\mathbb{F}_p$; let $\zeta$ be a root of the polynomial $x^4+1$ in $K$.

We note that $$(\zeta + \zeta^{-1})^2 = \zeta^2 + 2 + \zeta^{-2} = 2 + \zeta^{-2} (\zeta^{4} + 1) = 2 .$$ So $$(\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1}) 2^{(p-1)/2} = (\zeta + \zeta^{-1}) \genfrac{(}{)}{}{}{2}{p}.$$

On the other hand, since $K$ is a field of characteristic $p$, $$(\zeta + \zeta^{-1})^p = \zeta^p + \zeta^{-p} .$$ Thus $$\zeta^p + \zeta^{-p} = (\zeta + \zeta^{-1})^p = (\zeta + \zeta^{-1} \genfrac{(}{)}{}{}{2}{p} .$$ Now, if $p \equiv 4 \pm 1 \pmod{8}$, then $$\zeta^{p} + \zeta^{-p} = - ( \zeta + \zeta^{-1} )$$ and $p^2 - 1 \equiv 8 \pmod{16}$, so $(-1)^{(p^2-1)/8} = -1$, and $$\genfrac{(}{)}{}{}{2}{p} = -1 = (-1)^{(p^2 - 1)/8} .$$ On the other hand, if $p \equiv \pm 1 \pmod{8}$, then $$\zeta^p + \zeta^{-p} = \zeta + \zeta^{-1},$$ and $p^2 -1 \equiv 0 \pmod{16}$, so $$\genfrac{(}{)}{}{}{2}{p} = 1 = (-1)^{p^2-1} .$$ Thus the theorem holds in all cases. $\blacksquare$

References

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