Quadratic Reciprocity

MATH3301/3401 -Quadratic Reciprocity

This page - Gauss's Lemma Quadratic Reciprocity References

Gauss's Lemma

Whilst looking for a simple proof of the Law of Quadratic Reciprocity, Gauss (in 1808) discovered a lemma which now bears his name. Given an odd prime p and a residue a (mod p) which is prime to p, the lemma describes a necessary and sufficient condition for a to be a quadratic residue (mod p). Before stating the lemma, we need to recall some facts.

The p-1 integers ±1, ±2, ...,±(p-1)/2 form a reduced set of residues mod p. Consequently, for each x in the range 1 through (p-1)/2,

ax ≡ ±u_x (mod p)

where the integer u_x is again in the range 1 through (p-1)/2.
The numbers u_x (x = 1, 2, ..., (p-1)/2) are in fact distinct [Exercise: prove this] and are therefore the numbers 1, 2, ..., (p-1)/2 in some order.
Let M be the number of these congruences in which the sign is negative. We are now ready to state Gauss's lemma ...

Lemma - With the above notation, (a/p) = (-1)^M.

[In words: a is a quadratic residue (mod p) if, and only if, M is even.]

Proof We multiply together the (p-1)/2 congruences

ax ≡ ±u_x (mod p) (x = 1, ..., (p-1)/2)

to obtain

a^(p-1)/2.1.2....(p-1)/2 ≡ (-1)^M.1.2....(p-1)/2 (mod p).

[Recall that the u_x's are the numbers 1, ..., (p-1)/2 in some order.]
As the product 1.2....(p-1)/2 is prime to p, we may cancel it to obtain

a^(p-1)/2 ≡ (-1)^M (mod p).

We now use Euler's Criterion which states that

a^(p-1)/2 ≡ (a/p) (mod p).

As (a/p) = ±1 and p is odd, we conclude that (a/p) and (-1)^M must be equal:

(a/p) = (-1)^M.QED

Two examples of Gauss's lemma

p = 13	a = 3	x =	1	2	3	4	5	6
		ax =	3	6	9	12	15	18
		±u_x =	3	6	-4	-1	2	5	⇒ 3 is a square mod 13

p = 13	a = 7	x =	1	2	3	4	5	6
		ax =	7	14	21	28	35	42
		±u_x =	-6	1	-5	2	-4	3	⇒ 7 is a non-square mod 13

An important corollary

If p is any odd prime then

2 is a square mod p if p ≡ 1 or 7 (mod 8);

2 is a non-square mod p if p ≡ 3 or 5 (mod 8).

Proof Taking a = 2 in Gauss's lemma, we obtain

2 is a square mod p if, and only if, M is even.

To complete the proof, we need to determine M, ie the number of congruences

2x ≡ ±u_x (mod p) (x = 1, ..., (p-1)/2; 1 ≤ u_x ≤ (p-1)/2)

in which the sign is negative. It's not hard to see that the sign will be negative if, and only if, x lies in the range (p-1)/4 < x ≤ (p-1)/2. [See the examples below.] The number of integers in this range is precisely (p-1)/2 - [(p-1)/4] where [...] is the floor function. Thus

M = (p-1)/2 - [(p-1)/4].

As p is odd, there are just two cases to consider:

p = 4s+1.
Then M = (p-1)/2 - [(p-1)/4] = (2s) - [s] = s.
Thus M = (p-1)/4 which is even if, and only if, p ≡ 1 (mod 8).
p = 4s-1.
Then M = (p-1)/2 - [(p-1)/4] = (2s-1) - [s- 1/2] = (2s-1) - (s-1) = s.
Thus M = (p+1)/4 which is even if, and only if, p ≡ 7 (mod 8).

The corollary is now proved. QED
CommentThis corollary is usually stated in the form (2/p) = (-1)^(p²-1)/8.
[Exercise: Prove that the two ways of stating the corollary are equivalent.]

Some numerical examples of the corollary

p = 7	x =	1	2	3
≡ 7 (mod 8)	2x =	2	4	6
	±u_x =	2	-3	-1	⇒ M = 2 (2 is a square mod 7)

p = 11	x =	1	2	3	4	5
≡ 3 (mod 8)	2x =	2	4	6	8	10
	±u_x =	2	4	-5	-3	-1	⇒ M = 3 (2 is a non-square mod 11)

p = 13	x =	1	2	3	4	5	6
≡ 5 (mod 8)	2x =	2	4	6	8	10	12
	±u_x =	2	4	6	-5	-3	-1	⇒ M = 3 (2 is a non-square mod 13)

p = 17	x =	1	2	3	4	5	6	7	8
≡ 1 (mod 8)	2x =	2	4	6	8	10	12	14	16
	±u_x =	2	4	6	8	-7	-5	-3	-1	⇒ M = 4 (2 is a square mod 17)

Quadratic Reciprocity

In my view, one of the clearest expositions of the Law of Quadratic Reciprocity appears in "Number Theory for Beginners" by André Weil. Weil's proof of the Law works (like Eisenstein's proof) by counting integer points in a certain rectangle. My (slight) adaptation of Weil's proof makes explicit use of Gauss's lemma.

The Law of Quadratic Reciprocity (known to Euler but first proved by Gauss) states that

(p/q).(q/p) = (-1)^(p-1)(q-1)/4

where p and q are any distinct odd primes. Weil's proof uses the closed rectangular region R:

where

m = (p-1)/2, n = (q-1)/2. [As p and q are odd, m and n are integers.]

Proof(after Weil)

For x = 1, ..., m, we write the product qx as
qx = ε_xu_x + py_x
where ε_x = ±1, 1 ≤ u_x ≤ m, y_x ε Z.
Note -For reasons discussed earlier, the u_x's are the numbers 1, ..., m in some order.
We define M (see earlier) as the number of points (x, y_x) for which ε_x = -1. Noting that
ε_x = -1 if, and only if, py_x - qx = u_x if, and only if, 1 ≤ py_x - qx ≤ m,
M is just the number of points (x, y_x) satisfying the inequalities
1 ≤ x ≤m, 1 ≤ py_x - qx ≤ m.
These inequalities easily imply that 1 ≤ y_x ≤ n, showing that (x, y_x) lies in the rectangle R.
M is therefore the number of integer points (x, y) in the sub-region of R defined by the inequality
1 ≤ py - qx ≤ m [See diagram below].
Swapping the roles of the primes p and q, we now write
py = ε_yu_y + qx_y (y = 1, ..., n)
where ε_y = ±1, 1 ≤ u_y ≤ n, x_y ε Z.
Note -The u_y's are the numbers 1, ..., n in some order.
Next, we define N as the number of points (x_y, y) for which ε_y = -1.
Arguing as before, we find that N is the number of integer points (x, y) in the sub-region of the rectangle R defined by the inequalitiy
1 ≤ qx - py ≤ n [See diagram below].
Noting that R contains no integer points on the line py - qx = 0 (which separates the sub-regions of R defining M and N), we see that M + N is the number of integer points in the combined sub-region of R defined by the inequality
-n ≤ py - qx ≤ m.
The remaining integer points in R lie either in the region satisfying
py - qx < -n
or in the region satisfying
py - qx > m.
If S integer points of R lie in the first of these regions, and T lie in the second region, then
mn = M + N + S + T
because each side of this equation counts the total number of integer points in R:
We now show that S = T. To do this, Weil uses the substitution
x = m + 1 - x'
y = n + 1 - y'.
It has two easily verified properties:
1. The mapping σ sending (x, y) to (x', y') permutes the integer points in R;
2. py - qx + n = -py' + qx' + m, implying that
  py - qx < -n if, and only if, py' - qx' > m.
It follows that σ defines a one-to-one mapping from the set of integer points in the region defining S onto the set of integer points in the region defining T. Consequently S = T.
We have now shown that
(-1)^mn = (-1)^M+N+2S = (-1)^M+N.
To complete the proof of Quadratic Reciprocity it suffices to show that
(p/q) = (-1)^M and (q/p) = (-1)^N
[for then, (p/q).(q/p) = (-1)^M+N = (-1)^mn = (-1)^(p-1)(q-1)/4].
However, the last two equations follow immediately from Gauss's lemma. QED

References

Weil A., Number Theory for Beginners

Serre J-P., A Course in Arithmetic (for Eisenstein's 'Sine' proof of Quadratic Reciprocity)

Proofs of Quadratic Reciprocity (University of Heidelberg)

MATH3301/3401 home page