Skip to main content

Section 17.6 A Proof of Quadratic Reciprocity

You are most likely now exhausted by the many applications and uses of quadratic reciprocity. Now we must prove it.

Recall the statement (Theorem 17.4.1): For odd primes \(p\) and \(q\text{,}\) we have that

\begin{equation*} \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}} \end{equation*}

That is to say, the Legendre symbols are the same unless \(p\) and \(q\) are both of the form \(4k+3\text{.}\)

Before beginning, let's recall the tools we will need on our jouney. First, \(p\) and \(q\) are odd primes in the context of this proof. Also, we will use the criterion of Eisenstein's 17.2.8 used earlier in the chapter. With that in mind, let

\begin{equation*} R=\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor \end{equation*}

be the exponent in question, so that

\begin{equation*} \left(\frac{q}{p}\right)=(-1)^R\text{.} \end{equation*}

Subsection 17.6.1 Re-enter geometry

The key to our proof will be geometrically interpreting \(\left\lfloor\frac{qe}{p}\right\rfloor\text{.}\) We can think of it as being the biggest integer less than \(\frac{qe}{p}\text{,}\) which means we can think of it as an integer height.

The following features are present in the next graphic, which should clarify how we'll think of it geometrically. Each type of object is highlighted with a different color.

  • The line through the origin with slope \(q/p\) (dotted blue).

  • All the grid points in (not on) the box of width \(p\) and height \(q\) (box red, points black).

  • Points with even \(x\)-coordinate corresponding to the highest that one can get while staying under the line of slope \(q/p\) (points blue).

  • The box of width \(\frac{p-1}{2}\) and height \(\frac{q-1}{2}\) (green), which we'll need in a moment.

Representing \(\left\lfloor\frac{qe}{p}\right\rfloor\) geometrically
Figure 17.6.1. Representing \(\left\lfloor\frac{qe}{p}\right\rfloor\) geometrically

It should be clear that each blue stack has the same height as \(\left\lfloor\frac{qe}{p}\right\rfloor\) for some even \(e\text{.}\) Check that for the case (\(p=11, q=7\)) in Figure 17.6.1 we should have a total of

\begin{equation*} \left\lfloor\frac{7\cdot 2}{11}\right\rfloor+\left\lfloor\frac{7\cdot 4}{11}\right\rfloor+\left\lfloor\frac{7\cdot 6}{11}\right\rfloor+\left\lfloor\frac{7\cdot 8}{11}\right\rfloor+\left\lfloor\frac{7\cdot 10}{11}\right\rfloor = \end{equation*}
\begin{equation*} \left\lfloor\frac{14}{11} \right\rfloor+\left\lfloor\frac{28}{11} \right\rfloor+\left\lfloor\frac{42}{11} \right\rfloor+\left\lfloor\frac{56}{11} \right\rfloor+\left\lfloor\frac{70}{11} \right\rfloor = \end{equation*}
\begin{equation*} 1+2+3+5+6=17\equiv1\text{ (mod }2)\text{,} \end{equation*}

which makes sense since \(7\) and \(11\) are both congruent to \(3\) modulo four, so the Legendre symbols would be opposing.

The core point of the overall proof is to convince ourselves of the following geometric claim:

Along with Eisenstein, we call this second number \(\mu\text{.}\) One may note that

\begin{equation*} \mu = \sum_{f=1}^{(p-1)/2}\left\lfloor\frac{qf}{p}\right\rfloor\text{.} \end{equation*}

When I first saw this proof, it seemed pretty opaque. I highly recommend getting online and trying the interactive version of the graphic below to convince yourself of the plausibility of Claim 17.6.2, or at the very least that \(R\) and \(\mu\) really are given as claimed.

Once the geometry is out of the way, we are almost there.

Essentially all we do is take the previous claim and use it for both Legendre symbols; then we add and get the result. Let's see Claim 17.6.2 in action for each symbol.

  • First, to get \(\left(\frac{q}{p}\right)\text{,}\) we can safely ignore \(R\) to just focus on the number (indeed, parity) of \(\mu\text{,}\) the number of positive lattice points below the dotted line in and on the green box.

  • The same argument applies to \(\left(\frac{p}{q}\right)\text{;}\) we can safely ignore the exponent

    \begin{equation*} R'=\sum_{\text{even }e',\; 0<e'<q}\left\lfloor\frac{pe'}{q}\right\rfloor \end{equation*}

    and instead focus on the number (indeed, parity) of positive lattice points in and on the green box to the left of the dotted line, which we may for convenience call \(\mu'\text{.}\)

A useful way to think about this is that the previous two steps switch the role of the vertical and horizontal axes.

Now consider the total exponent of \(-1\) we expect from \(\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)\text{.}\) It will be the sum of those two amounts \(\mu+\mu'\) – which, geometrically, is the number of (positive, still) points in and on the green box. (There is no overlap, because \(q\) and \(p\) are coprime, so there are no lattice points on the dotted line until we get to \((p,q)\text{,}\) which is well outside the green box.)

How many total points is this? The green box, by design, has dimensions \(\frac{p-1}{2}\) and \(\frac{q-1}{2}\text{,}\) so that would mean

\begin{equation*} \frac{p-1}{2}\cdot\frac{q-1}{2}\equiv \sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor+\sum_{\text{even }e',\; 0<e'<q}\left\lfloor\frac{pe'}{q}\right\rfloor\text{ (mod }2)\text{,} \end{equation*}

so that

\begin{equation*} \left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{R+R'}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\text{.} \end{equation*}

Subsection 17.6.2 Proving proper parity

So to finish the proof via Claim 17.6.2, we must show that the number of blue points (points under the line with even \(x\)-coordinate) has the same parity as the number of positive points in the green box under the line. Equivalently, we will show \(R\equiv \mu\) (mod \(2\)).

In the next graphic, there is a lot going on, all of which we will use for the proof (note especially the new, green, points). We will clarify each of the pieces below.

The full picture of proof of QR
Figure 17.6.4. The full picture of proof of QR

Combined with our previous knowledge, can you check the blue and green dots in the small triangle represent

\begin{equation*} \mu=\left\lfloor\frac{7\cdot 1}{11}\right\rfloor+\left\lfloor\frac{7\cdot 2}{11}\right\rfloor+\left\lfloor\frac{7\cdot 3}{11}\right\rfloor+\left\lfloor\frac{7\cdot 4}{11}\right\rfloor+\left\lfloor\frac{7\cdot 5}{11}\right\rfloor\text{?} \end{equation*}

Let's take a closer look at the two sets of green dots.

  • One set is on top, the lattice points with even \(x\)-coordinates greater than \(\frac{p-1}{2}\) which have \(y\)-coordinate less than \(q\) which are above the dotted line.

  • The other set is similar, but on the bottom, with odd positive \(x\)-coordinates less than \(\frac{p-1}{2}\) which have positive \(y\)-coordinate and are below the line.

You can think of the first set as filling in the even columns greater than \(\frac{p-1}{2}\text{,}\) while the latter set fills in the triangle for odd columns less than \(\frac{p-1}{2}\) (in both cases, strictly inside the red box of size \(p\) by \(q\)). To further understand this, in the interactive form of the text you may wish to try \(q\) relatively large compared to \(p\) to see this more clearly. Try several different values!

The key observation is that these two sets of green dots are symmetric images – they are simply rotated around the point

\begin{equation*} \left(\frac{p}{2},\frac{q}{2}\right)\text{.} \end{equation*}

This makes sense, since with \(p\) and \(q\) odd, this would change odd to even and vice versa.

So in order to say that \(\mu\) has the same parity as \(R\) (which is our goal to finish the proof), we just have to show that either set of green points has the same parity as that of the set of blue points outside the green box. Again, refer to the interactive graphic and try it with different primes for best understanding.

There are \(q-1\) points in each column of points outside the green box. In particular, there an even number of points in each such column.

So whether the number of blue points in a given column is even or odd, it is guaranteed that the parity of the green points in that same column is also even or odd, respectively. So the parity of the green points outside the green box is the same as the parity of the blue points outside the green box.

This means the parity of the points inside the triangle \((\mu)\) is the same as that of the blue points (\(R\)), which is what we wanted to prove!

Subsection 17.6.3 Postlude

It's really quite amazing how we needed to understand congruence, parity, some geometry, and of course the idea of a quadratic residue in the first place to prove this. As of right now, there is a list of well over two hundred proofs of this theorem. The very shortest might be one by G. Rousseau, and there is a nice list online of “favorite proofs” by various mathematicians.

So this is one proof where it is appropriate to say Q.E.D.