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 nonquadratic 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 a symbol to represent this information, which we will denote as 

_{} 

Thus [p\q] equals either +1 or 1 depending on whether p is or isn't a square modulo 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 4k1, in which case [p\q] = [q\p]. This is a remarkable fact, and not at all selfevident. Legendre succeeded in proving some 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 incomplete. 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 proofs. 

First, notice that the theorem can be expressed algebraically as 

_{} 

since the exponent on 1 is even if and only if both p and q are of the form 4k1. 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 (p1)(q1)/4 "lattice points", i.e., points (x,y) with integer coordinates. 

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

_{} 

These lines partition the rectangle 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 

_{} 

so we can rewrite our theorem (1) in the equivalent form 

_{} 

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 

_{} 

This equality would certainly hold if we could show that 

_{} 

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 righthand 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 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 

_{} 

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

_{} 

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 any prime p, we know that for each integer x = 1, 2, .., p1 there is a unique integer y (distinct from x) in the range from 1 to p1 such that xy = a. Thus we have a partition of all the nonzero residues (mod p) into (p1)/2 pairs (x,y), each of whose product is "a", so we can multiply them together to give 

_{} 

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 righthand equality (4) as a congruence 

_{} 

To prove this, we draw another line on our lattice, with the equation 

_{} 

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 p1 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 (p1)/2 there is a unique integer y[x] (from the range 1 to (q1)/2) such that the point (x,y) falls within the region y = (q/p)x ± 1/2. 

For each of those (p1)/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 pyqx = pYqX 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 (p1)/2, this requires x = X and therefore y = Y. 

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

_{} 

We also have the product 

_{} 

If we replace qx in the lefthand product by py[x]  (py[x]  qx) and evaluate modulo p we have 

_{} 

Now, notice that the quantity in parentheses in the lefthand 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 evaluate the product in terms of the absolute values, and then set the sign of the overall product to (1)^{P{R2}}. Consequently we have 

_{} 

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

_{} 

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. 
