The Jewel of Arithmetic: Quadratic Reciprocity

It's easy to find integer solutions of the equation y^2 = 2x^2 + 7k,
but there are no integer solutions at all of the seemingly similar
equation y^2 = 3x^2 + 7k.  This is the sort of thing that experienced
number theorists can tell at a glance, simply by noting that the
equations written modulo 7 are y^2 = 2x^2 and y^2 = 3x^2 respectively,
and since division is unique in the field of integers (mod p) we 
have (y/x)^2 = n (mod p), which implies that n must be the square 
of some element of the field of integers modulo p.  But the integers
mod 7 are just 0,1,2,3,4,5,6, whose squares (mod 7) are 0,1,4,2,2,4,1.
Thus the equation y^2 = nx^2 + 7k can have integer solutions only if
n is congruent to 0, 1, 2, or 4 (mod 7).  These are called the 
quadratic residues (mod 7), and the remaining numbers 3,5,6 are 
called the non-quadratic residues.

It's often extremely important when dealing with problems in number
theory to know whether a certain prime p is a square (i.e., a 
quadratic residue) modulo some other particular prime q.  (For an 
example, see the note on Fermat's Last Theorem for Cubes.)  Legendre 
defined the symbol

            / p \       /  +1   if p is a square (mod q)
           ( --- )  =  (
            \ q /       \  -1   if p is NOT a square (mod q)

This is not to be confused with the ratio of p over q.  It's just an 
abstract symbol equal to either +1 or -1 depending on whether p is or 
isn't a square modulo q.  For purposes of typing in ASCII, we'll write
this symbol in line as [p\q].

From examining many individual cases, Euler had previously noticed a 
striking relationship between the [p\q] and [q/p].  Specifically, he
noticed that [p\q] = [q/p] except when p and q are both of the form
4k-1, in which case [p\q] = -[q/p].  This is a remarkable result, and
not at all self-evident.  Legendre succeeded in proving somes special
cases of this, and also gave what he thought was a complete proof,
but his argument relied on the premise that every arithmetic 
progression contains infinitely many primes.  This is in fact true,
as subsequently shown by Dirichlet, but at the time of Legendre's
proof it wasn't known, so Gauss pointed out that Legendre's proof
was not valid.  Gauss went even further, and gave several (valid)
proofs of this remarkable theorem, which he called the Fundamental
Theorem of number theory.  Following is an explanation of one his
his proofs.

First, notice that the theorem can be expressed numerically as

            / p \  / q \          (p-1)(q-1)/4
           ( --- )( --- )  =  (-1)
            \ q /  \ p /       

since the exponent on -1 is even unless both p and q are of the
form 4k-1.  To prove this theorem, consider the rectangular region
of the xy plane where x ranges from 1/2 to p/2 and y ranges from
1/2 to q/2.  This region obviously contains (p-1)(q-1)/4 "lattice
points", i.e., points (x,y) with integer coordinates.

Now we draw three parallel lines through this rectangular region,
with the equations 

   y = (q/p)x        y = (q/p)x + 1/2        y = (q/p)x - q/(2p)

These lines partition the rectange into four separate regions, which
we will call R1, R2, R3, and R4 (from top to bottom).  This is 
illustrated below for the case p=11, q=17.

      

If we let P(R) denote the number of lattice points in the region R,
then we have 
                                          (p-1)(q-1)
        P(R1) + P(R2) + P(R3) + P(R4)  =  ----------
                                               4

so we can re-write our theorem in the equivalent form

            / p \  / q \          P(R1) + P(R2) + P(R3) + P(R4)
           ( --- )( --- )  =  (-1)
            \ q /  \ p /       

Furthermore, it's easy to see that the upper and lower regions (R1
and R4) are symmetrical with respect to the lattice, so they both
contain the same number of lattice points.  (For example, in the
above figure, we have P(R1) = P(R2) = 16.)  Consequently, the sum
of the number of lattice points in these two regions is always an
even number, which means they (jointly) have no effect the parity 
of the exponent on -1.  Thus they can be omitted, and we have the
equivalent form

            / p \  / q \          P(R2) + P(R3)
           ( --- )( --- )  =  (-1)
            \ q /  \ p /       

This equality would certainly hold if we could show that

     / p \          P(R3)          / q \          P(R2)
    ( --- )  =  (-1)              ( --- )  =  (-1)                (1)
     \ q /                         \ p /       

Now, since our choice of p and q was arbitrary, we could swap them
and arrive at the transposed conditions, so we really only need to
prove one of these, and then the other will be implied by symmetry.
We will prove the right-hand equality.

First we need to prove Euler's Criterion, which gives a useful
congruence condition on the Legendre symbols.  Recall that Fermat's
little theorem states a^(p-1) = 1 (mod p) for any integer a coprime
to p.  Obviously if we take the square root of both sides of this
congruence we have a^((p-1)/2) = +-1 (mod p), but the question is,
how do we determine the sign of this square root of 1?  Euler pointed
out that it is simply the Legendre symbol, i.e., we have

                  (p-1)/2      / a \
                 a         =  ( --- )   (mod p)
                               \ p /

To prove this, first assume that [a\p] = +1, in which case there is
an element x of the integers (mod p) such that x^2 = a (mod p), so
we have

                 (p-1)/2      (p-1)
                a         =  x       =  1   (mod p)

by Fermat's Little Theorem.  Hence, in this case it's clear that
a^((p-1)/2 is congruent to [a\p] modulo p.  On the other hand, suppose
that [a\p] = -1, which means there does NOT exist an integer x such
that x^2 = a (mod p).  In this case we note that, due to unique
division in the field of integers modulo a prime p, we know that
for each integer x=1,2,..,p-1 there is a unique integer y (distinct
from x) in the range from 1 to p-1 such that xy = a.  Thus we have
a partition of all the non-zero residues (mod p) into (p-1)/2 pairs 
(x,y), each of whose product is "a", so we can multiply them together
to give
                               (p-1)/2
                  (p-1)!  =  a              (mod p)

and by Wilson's Theorem this is -1 (mod p), so again we have [a\p]
equal to a^((p-1)/2).

So now we can restate the right-hand equality (1) as a congruence

                 P(R2)        (p-1)/2
             (-1)         =  q             (mod p)
                  
To prove this, we draw another line on our lattice, with the equation

                        y = (q/p)x - 1/2

This is symmetrical about y=(q/p)x to the line y = (q/p)x + 1/2 that 
already formed one of the boundaries of the region R2.  It is the 
line shown in red on the above illustration.  At each integer value 
of x from 1 to p-1 the region in between these two lines has a height 
of 1, so it contains precisely one lattice point whose y component 
is the nearest integer to qx/p.  Thus for each integer x from 1 to
(p-1)/2 there is a unique integer y[x] (from the range 1 to (q-1)/2)
such that the point (x,y) falls within the region y = (q/p)x +- 1/2.

For each of those (p-1)/2 lattice points (x,y[x]), consider the 
quantity |py[x] - qx|.  It's clear that this has a distinct value 
on each of these lattice points, because if there was another lattice 
point (X,Y[X]) in the same region such that |py-qx| = |pY-qX| then we 
would have p(y+-Y) = q(x+-X), which implies that p divides (x+-X), 
but since x and X are both in the range 1 to (p-1)/2, this requires 
x=X and therefore y=Y.

So, we have (p-1)/2 distinct integer values of |py[x] - qx|, all in 
the range from 1 to (p-1)/2 (as seen by multiplying through the two
boundary line equations by p to give p/2 > py-qx > -p/2).  Therefore
the product of these quantities is

             ((p-1)/2
              PROD   |py[x] - qx|  =  ((p-1)/2)!
               x=1

We also have the product

             ((p-1)/2        (p-1)/2
              PROD   qx  =  q       ((p-1)/2)!
               x=1

If we replace q in the left-hand product by py[x] - (py[x] - qx)
and evaluate modulo p we have

      ((p-1)/2                   (p-1)/2
       PROD   -(py[x] - qx)  =  q       ((p-1)/2)!        (mod p)
        x=1

Now, notice that the quantity in parentheses in the left-hand product
is positive precisely for those lattice points in our original region
R2, i.e., the points that are above the line y = (q/p)x.  Hence we
can evlauate the product in terms of the absolute values, and then
set the sign of the overall product to (-1)^P(R2).  Consequently we
have
           P(R2)                (p-1)/2
       (-1)     ((p-1)/2)!  =  q       ((p-1)/2)!        (mod p)

Obviously ((p-1)/2)! is coprime to p, so we can divide by that
quantity to give the result

                   P(R2)       (p-1)/2
               (-1)        =  q               (mod p)

By Euler's Criterion this shows that (-1)^P(R2) is congruent (and 
therefore equal) to [q\p].  As noted above, by interchanging p and
q we can similarly prove that (-1)^P(R3) (with the present definition
of R3) equals [p\q], so this completes the proof of the law of
quadratic reciprocity.