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:

(7/3) = -(3/7) (11/3) = -(3/11) (11/7) = - (7/11) (19/3) = -(3/19) (19/7) = -(7/19) (19/11) = -(11/19) (5/3) = (3/3) - - - - - (7/5) = (5/7) - - - - (11/5) = (5/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/5) = (5/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.