The Quadratic Reciprocity Theorem

We are now going to observe a relationship between the Legendre symbols $(p/q)$ and $(q/p)$ where p and q are odd primes. First, let's start looking at the relationship between the Legendre symbols of two odd primes with the following table showing the Legendre symbol $(p/q)$ from p = 19 to q = 17.

$(p/q)$	p = 5	p = 7	p = 11	p = 13	p = 17	p = 19
q = 3	- 1	1	-1	1	-1	1
q = 5	-	-1	1	-1	-1	1
q = 7	-	-	1	-1	-1	-1
q = 11	-	-	-	-1	-1	-1
q = 13	-	-	-	-	1	-1
q = 17	-	-	-	-	-	1

And now lets look at the next table showing the Legendre symbol $(q/p)$ from p = 19 to q = 17. The additional highlighted entries are different from $(p/q)$:

$(q/p)$	q = 5	q = 7	q = 11	q = 13	q = 17	q = 19
p = 3	- 1	-1	1	1	-1	-1
p = 5	-	-1	1	-1	-1	1
p = 7	-	-	-1	-1	-1	1
p = 11	-	-	-	-1	-1	1
p = 13	-	-	-	-	1	-1
p = 17	-	-	-	-	-	1

From these tables, we deduce the following relationships from these Legendre symbols:

(5/3) = (3/3)	-	-	-	-	-
(7/3) = -(3/7)	(7/5) = (5/7)	-	-	-	-
(11/3) = -(3/11)	(11/5) = (5/11)	(11/7) = - (7/11)	-	-	-
(13/3) = (3/13)	(13/5) = (5/13)	(13/7) = (7/13)	(13/11) = (11/13)	-	-
(17/3) = (3/17)	(17/5) = (5/17)	(17/7) = (7/17)	(17/11) = (11/17)	(17/13) = (13/17)	-
(19/3) = -(3/19)	(19/5) = (5/19)	(19/7) = -(7/19)	(19/11) = -(11/19)	(19/13) = (13/19)	(19/17) = (17/19)

We can deduce $(p/q) = -(q/p)$ if $p \equiv q \equiv 3 \pmod 4$. If just one of p or q is congruence to 1 (mod 4), then we can deduce that $(p/q) = (q/p)$. We will summarize this in the Quadratic Reciprocity theorem.

Theorem: If the primes p and q are odd and $p \equiv q \equiv 3 \pmod 4$, then the Legendre symbols $(p/q) = -(q/p)$, otherwise $(p/q) = (q/p)$.

Proof of the Quadratic Reciprocity Theorem

We can restate the Quadratic Reciprocity theorem in the following way:

Theorem: If the primes p and q are odd, then $(p/q)(q/p) = ( -1)^{\frac{(p-1)(q-1)}{4}}$, or more appropriately, $( -1)^{\frac{(p-1)(q-1)}{4}} = -1$ if and only if $p \equiv q \equiv 3 \pmod 4$, and $( -1)^{\frac{(p-1)(q-1)}{4}} = 1$ otherwise.

We will now prove this theorem using some of the other lemmas we have looked at thus far.

• Proof: Of the list $q, 2q, 3q, ..., \frac{p - 1}{2} q$, let the list $R = r_1, r_2, ..., r_z$ be the list of least residues that less or equal to $\frac{p - 1}{2}$, and let the list $S = s_1, s_2, ..., s_g$ be the list of least residues that are strictly greater than $\frac{p - 1}{2}$.

• We know that $r_1 + r_2 + ... + r_z + (p - s_1) + (p - s_2) + ... + (p - s_g) = 1 + 2 + 3 + ... + \frac{p - 1}{2}$. We will now use the following geometric equivalence to rewrite the righthand side of this equation:

(1)

\begin{align} 1 + 2 + 3 + ... + n = \frac{n(n - 1)}{2} \end{align}

• That is, $r_1 + r_2 + ... + r_z + (p - s_1) + (p - s_2) + ... + (p - s_g) = \frac{\frac{p - 1}{2} \cdot \frac{p + 1}{2}}{2} = \frac{1}{8}(p^2 - 1)$. Notice that we can rewrite the lefthand side of this equation though, that is:

(2)

\begin{align} R + gp - S = \frac{p^2 - 1}{8} \end{align}

• Now we're going to formulate another relation. Now that:

(3)

\begin{align} \sum_{k = 1}^{\frac{p -1}{2}} kq = q \sum_{k = 1}^{\frac{p -1}{2}} k = q(\frac{(p^2 - 1)}{8} \end{align}

• Now let $t_i$ be the least residue (mod p) of $iq$. It thus follows that $iq = \left \lfloor \frac{iq}{p} \right \rfloor p + t_i$, or more appropriately:

(4)

\begin{align} \sum_{k = 1}^{\frac{p - 1}{2}} = \sum_{k = 1}^{\frac{p - 1}{2}} \left \lfloor \frac{kq}{p} \right \rfloor p + \sum_{k = 1}^{\frac{p - 1}{2}} t_k = p \: S(p, q) + (R + S) \end{align}

• So then it follows that:

(5)

\begin{align} q^{\frac{p^2 - 1}{8}} = p \: S(p, q) + R + S \end{align}

• Now we have that from earlier $R + gp - S = \frac{p^2 - 1}{8}$, which can be rewritten as $R = \frac{p^2 - 1}{8} + S - gp$. Substituting this into our other equation, we get that:

(6)

\begin{align} q^{\frac{p^2 - 1}{8}} = p \: S(p, q) + \frac{p^2 - 1}{8} + S - gp + S \\ q^{\frac{p^2 - 1}{8}} = p \: S(p, q) + \frac{p^2 - 1}{8} + - gp + 2S \\ (q - 1)^{\frac{p^2 - 1}{8}} = p(S(p, q) - g) + 2S \\ \end{align}

• Now we know that $(q - 1)^{\frac{p^2 - 1}{8}}$ is even, and that $2S$ is even. Hence $p(S(p, q) - g)$ must also be even. Since p is an odd prime, then $(S(p, q) - g )$ must be even, so it follows that either $S(p, q)$ and $-g$ are both odd or both even. Hence:

(7)

\begin{align} S(p, q) \equiv g \pmod 2 \end{align}

• So then:

(8)

\begin{align} (q/p) = (-1)^{S(p,q) + S(q, p)} = (-1)^{\frac{(p-1)(q - 1)}{4}} \end{align}

• And we are done the proof.