Quadratic Reciprocity


It's easy to find integer solutions of the equation y2 = 2x2 + 7k, but there are no integer solutions at all of the seemingly similar equation y2 = 3x2 + 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 y2 = 2x2 and y2 = 3x2 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 y2 = nx2 + 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 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 4k-1, in which case [p\q] = -[q\p]. This is a remarkable fact, and not at all self-evident. 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 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



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 re-write 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 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 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 x2 = 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 x2 = 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, .., 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



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



We also have the product



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



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 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 ((p-1)/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.


Return to MathPages Main Menu