# 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:

- 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:

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

- 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:

- So then it follows that:

- 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:

- 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:

- So then:

- And we are done the proof.