Section17.6A Proof of Quadratic Reciprocity
You are most likely now exhausted by the many applications and uses of quadratic reciprocity. Recall the statement: For odd primes \(p\) and \(q\), we have that \[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\] That is to say, the Legendre symbols are the same unless \(p\) and \(q\) are both of the form \(4k+3\).
Before beginning, let's recall the baggage we will need on our jouney. First, recall that \(p\) and \(q\) are odd primes in the context of this proof. Also, we will use the criterion of Eisenstein's we've used throughout, where we let \[R=\sum_{\text{even }e,\; 0<e<p}\left\lfloor\frac{qe}{p}\right\rfloor\; \] be the exponent in question, so that \[\left(\frac{q}{p}\right)=(-1)^R\; .\]
Subsection17.6.1Re-enter geometry
The key will be geometrically interpreting \(\left\lfloor\frac{qe}{p}\right\rfloor\). We can think of it as being the biggest integer less than \(\frac{qe}{p}\), 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 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.
It should be clear that each blue stack has the same height as \(\left\lfloor\frac{qe}{p}\right\rfloor\) for some even \(e\). The core geometric point of the proof is to convince ourselves that the number of blue points has the same parity as the total number of (positive) points in and on the green box which are under the dotted line.
Subsection17.6.2What steps would remain
Suppose that we have proved that the number of blue points has the same parity as the (positive) points in the “triangle” in question. If we can do that, the following steps finish the proof of quadratic reciprocity.
Claim17.6.1
The following steps would definitely complete the proof of quadratic reciprocity.
- First, to get \(\left(\frac{q}{p}\right)\), we can ignore \(R\) and just focus on the number (indeed, parity) of positive lattice points in that more-or-less triangle.
- Then the same argument applies to \(\left(\frac{p}{q}\right)\); we could ignore its crazy exponent (call it \(R'\), if you must) and instead focus on the number of positive lattice points in and on the green box to the right of the dotted line. (We've switched the role of \(x\) and \(y\), so “above the \(y\)-axis” means to its right.)
- So the exponent of \(-1\) we expect from \(\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)\) is just the sum of those two amounts. That is, the exponent is the number of 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)\).)
- You'll note that this box has dimensions \(\frac{p-1}{2}\) and \(\frac{q-1}{2}\), so that would mean \[\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 }f,\; 0<f<q}\left\lfloor\frac{pf}{q}\right\rfloor\text{ mod }(2)\; ,\] so that \[\left(\frac{q}{p}\right)\left(\frac{p}{q}\right)=(-1)^{R+R'}=(-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}\; .\]
Subsection17.6.3Proving proper parity
So we must show that the number of blue points (points under the line with even \(x\)-coordinate) is the same as the number of positive points in the green box under the line. Along with Eisenstein, we call this second number \(\mu\). In the next graphic, there is a lot going on, but we will clarify each of the pieces below.
Let's look at the two sets of green dots.
- The ones on top are the ones with even \(x\)-coordinates greater than \(\frac{p-1}{2}\) which have \(y\)-coordinate less than \(q\) and are above the line.
- (You can think of them as filling in the even columns greater than \(\frac{p-1}{2}\).)
- The ones on the bottom are the ones with odd \(x\)-coordinates less than \(\frac{p-1}{2}\) which have \(y\)-coordinate greater than \(0\) and are below the line.
- (You can think of them as filling in the the triangle for odd columns less than \(\frac{p-1}{2}\).)
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 \[\left(\frac{p}{2},\frac{q}{2}\right)\; .\] 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.
Claim17.6.2
Either set of green points has the same parity as the set of blue points outside the green box.Proof
- 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!
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 this one by G. Rousseau, and here is a nice list of “favorite proofs” by various mathematicians.
So this is one proof where it is appropriate to say Q.E.D.
