Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section17.6A 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: For odd primes \(p\) and \(q\), 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\).

Before beginning, let's recall the tools 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 17.2.8 we've used throughout. So we'll 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\; .\end{equation*}

Subsection17.6.1Re-enter geometry

The key to our proof 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 of this:

Proof

Subsection17.6.2Proving proper parity

So to finish the proof via Claim 17.6.1, 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, all of which we will use for the proof (note especially the new, green, points). We will clarify each of the pieces below.

Let's 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 \(x\)-coordinates less than \(\frac{p-1}{2}\) which have \(y\)-coordinate greater than \(0\) and are below the line.

You can think of the first set as filling in the even columns greater than \(\frac{p-1}{2}\), while the latter set fills in the the triangle for odd columns less than \(\frac{p-1}{2}\). 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)\; .\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.

Proof

Subsection17.6.3Postlude

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.