Section 17.6 A Proof of Quadratic Reciprocity
Subsection 17.6.1 Re-enter geometry
The key to our proof will be geometrically interpretingThe line through the origin with slope
(dotted blue).All the grid points in (not on) the box of width
and height (box red, points black).Points with even
-coordinate corresponding to the highest that one can get while staying under the line of slope (points blue).The box of width
and height (green), which we'll need in a moment.

Claim 17.6.2.
The number of blue points (which is
Proof.
See Subsection 17.6.2.
xxxxxxxxxx
def _(p=(11,prime_range(3,100)),q=(7,prime_range(3,100))):
E = [2,4..p-1]
plot4 = plot((q/p)*x,(x,0,p),linestyle='--')
plot3 = line([[0,0],[p,0],[p,q],[0,q],[0,0]], rgbcolor=(1,0,0))
plot2 = line([[0,0], [(p-1)/2,0], [(p-1)/2,(q-1)/2], [0,(q-1)/2], [0,0]], color='green')
grid_pts_1 = [[i,j] for i in [1..p-1] for j in [1..q-1]]
grid_pts_2 = [[i,j] for i in [1..(p-1)/2] for j in [1..(q-1)/2]]
plot_grid_pts = points(grid_pts_1,rgbcolor=(0,0,0),pointsize=10)
lattice_pts1 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<p and coords[0] in E)]
if len(lattice_pts1)!=0:
plot_lattice_pts1 = points(lattice_pts1, rgbcolor = (0,0,1),pointsize=20)
else:
plot_lattice_pts1 = Graphics()
show(plot2+plot3+plot4 + plot_grid_pts + plot_lattice_pts1, xmax=p,ymax=q,ymin=0)
forms = '$'+'+'.join([r'\left\lfloor\frac{%s\cdot %s}{%s}\right\rfloor'%(q,e,p) for e in E])+'$'
pretty_print(html("The blue dots represent "+forms))
forms2 = '$'+'+'.join([r'\left\lfloor\frac{%s}{%s} \right\rfloor'%(q*e,p) for e in E])
forms3 = '+'.join(['%s'%(floor(q*e/p)) for e in E])+r'=%s\equiv%s\text{ (mod }2)$'%(sum([floor(q*e/p) for e in E]),sum([floor(q*e/p) for e in E])%2)
pretty_print(html("This simplifies to "+forms2+'='+forms3))
Claim 17.6.3.
Suppose that we have proved Claim 17.6.2. Then we can quickly prove Quadratic Reciprocity.
Proof.
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
so that
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
One set is on top, the lattice points with even
-coordinates greater than which have -coordinate less than which are above the dotted line.The other set is similar, but on the bottom, with odd positive
-coordinates less than which have positive -coordinate and are below the line.
xxxxxxxxxx
def _(p=(11,prime_range(3,100)),q=(7,prime_range(3,100))):
E = [2,4..p-1]
plot4 = plot((q/p)*x,(x,0,p),linestyle='--')
plot3 = line([[0,0],[p,0],[p,q],[0,q],[0,0]], rgbcolor=(1,0,0))
plot2 = line([[0,0], [(p-1)/2,0], [(p-1)/2,(q-1)/2], [0,(q-1)/2], [0,0]], color='green')
grid_pts_1 = [[i,j] for i in [1..p-1] for j in [1..q-1]]
grid_pts_2 = [[i,j] for i in [1..(p-1)/2] for j in [1..(q-1)/2]]
plot_grid_pts = points(grid_pts_1,rgbcolor=(0,0,0),pointsize=10)
lattice_pts1 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<p and coords[0] in E)]
lattice_pts2 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p<0 and coords[0]>(p-1)/2 and coords[1]<q and coords[0] in E)]
lattice_pts3 = [coords for coords in grid_pts_1 if (coords[0]*q-coords[1]*p>0 and coords[0]<=(p-1)/2 and coords[0] not in E)]
if len(lattice_pts1)!=0:
plot_lattice_pts1 = points(lattice_pts1, rgbcolor = (0,0,1),pointsize=20)
else:
plot_lattice_pts1 = Graphics()
if len(lattice_pts2)!=0:
plot_lattice_pts2 = points(lattice_pts2, rgbcolor = (0,.5,0),pointsize=20)
else:
plot_lattice_pts2 = Graphics()
if len(lattice_pts3)!=0:
plot_lattice_pts3 = points(lattice_pts3, rgbcolor = (0,.5,0),pointsize=20)
else:
plot_lattice_pts3 = Graphics()
show(plot2+plot3+plot4 + plot_grid_pts+plot_lattice_pts1 + plot_lattice_pts2 + plot_lattice_pts3, xmax=p,ymax=q,ymin=0)
forms = r'$\mu='+'+'.join([r'\left\lfloor\frac{%s\cdot %s}{%s}\right\rfloor'%(q,e,p) for e in [1..(p-1)/2]])+'$'
pretty_print(html("The blue and green dots in the small triangle represent"))
pretty_print(html("the sum "+forms))
Claim 17.6.5.
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.