MAS3008 NUMBER THEORY

GAUSS’ LEMMA & QUADRATIC RECIPROCITY

Gauss’ Lemma

Let p be an odd prime and let a ∈ ℤ with gcd(a, p) = 1. Consider the least residues mod p of the (p − 1)/2 numbers ka, k = 1, 2, …, (p − 1)/2. (So these numbers lie in {−(p − 1)/2, …, (p − 1)/2}.) Suppose that s of these are negative. Then

(\frac{a}{p}) = (−1)^{s}.

Proof: Let these residues be u_{1}, …, u_{r} > 0 and −v_{1}, … − v_{s} < 0. Thus r + s = (p − 1)/2 and 1 ≤ u_{1}, …, u_{r}, v_{1}, … v_{s} ≤ (p − 1)/2.

The numbers u_{1}, …, u_{r}, v_{1}, … v_{s} are all different since

1. if u_{i} = u_{j} with i ≠ j then we have ka ≡ la (mod p) for some k, l, with 1 ≤ k < l ≤ (p − 1)/2, which is impossible as p |̸a.

2. if v_{i} = v_{j} with i ≠ j then we have −ka ≡ −la (mod p) for some k, l, with 1 ≤ k < l ≤ (p − 1)/2, which is impossible as p |̸a.

3. if u_{i} = v_{j} for some i, j then we have ka ≡ −la (mod p) for some k, l with 1 ≤ k, l ≤ (p − 1)/2. But this implies that k + l ≡ 0 (mod p), which is again impossible.

It follows that the numbers u_{1}, …, u_{r}, v_{1}, … v_{s} are precisely the numbers 1, 2, … (p − 1)/2 in some order, so that

(∏_{i=1}^{r} u_{i}) (∏_{j=1}^{s} v_{j}) = (\frac{p − 1}{2})!.

Thus

∏_{k=1}^{(p−1)/2}(ka) ≡ (∏_{i=1}^{r} u_{i}) (∏_{j=1}^{s}(−v_{j})) ≡ (−1)^{s} (\frac{p − 1}{2})! (mod p).

On the other hand, using Euler’s criterion, we have

∏_{k=1}^{(p−1)/2}(ka) = a^{(p−1)/2} ∏_{k=1}^{(p−1)/2} k

≡ (\frac{a}{p}) (\frac{p − 1}{2})!.

Thus we have

(\frac{a}{p}) ≡ (−1)^{s} (mod p),

and this must be an equality (rather than just a congruence mod p) since both sides are ±1. □

Theorem (Quadratic Reciprocity)

Let p and q be distinct odd primes. Then

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{((p−1)/2)·((q−1)/2)}.

Proof:

Call a point (x, y) in the plane a lattice point if x, y ∈ ℤ. We will consider the lattice points inside or on the edges of the rectangle with horizontal sides y = 1, (q − 1)/2 and vertical sides x = 1, (p − 1)/2. Clearly the number of such lattice points is

\frac{(p − 1)}{2} · \frac{(q − 1)}{2}.

The three lines shown are:

L :  y = \frac{q}{p}x,  i.e. x = \frac{p}{q}y.

L_{1} : y = \frac{q}{p}x + \frac{1}{2}.

L_{2} : x = \frac{p}{q}y + \frac{1}{2}.

Note that the diagram is symmetric under swapping x and y; p and q; L_{1} and L_{2}.

None of the lattice points in or on the rectangle lie on any of the lines L, L_{1}, L_{2}: for x, y ∈ ℤ we have

(x, y) ∈ L ⇒ py = qx ⇒ p|x;
(x, y) ∈ L_{1} ⇒ 2py = 2qx + p ⇒ p|x;
(x, y) ∈ L_{2} ⇒ 2qx = 2py + q ⇒ q|y;

and in each case this shows that (x, y) cannot lie in or on the rectangle. Thus each of the (p − 1)/2 · (q − 1)/2 lattice points is in one of the regions A, B, C_{1}, C_{2} (where A and B include points on the edges of the rectangle). We claim:

(i) A and B contain the same number of lattice points, m say;

(ii) C_{1} contains s_{1} lattice points, where (\frac{q}{p}) = (−1)^{s_{1}};

(iii) C_{2} contains s_{2} lattice points, where (\frac{p}{q}) = (−1)^{s_{2}}.

Assuming this, we have

(\frac{p − 1}{2}) (\frac{q − 1}{2}) = Number of lattice points in/on rectangle = s_{1}+s_{2}+2m,

so

(\frac{p}{q}) (\frac{q}{p}) = (−1)^{s_{1}+s_{2}} = (−1)^{s_{1}+s_{2}+2m} = (−1)^{(p−1)/2·(q−1)/2}

as required.

To prove the claim:

(i) A and B contain the same number of lattice points because, by symmetry, we can rotate the rectangle by 180 degrees about its centre

R = ((p + 1)/4, (q + 1)/4).

In detail, the transformation

(x, y) ↦ (x^{∗}, y^{∗}) = ((p + 1)/2 − x, (q + 1)/2 − y)

takes lattice points to lattice points, and takes the rectangle to itself:

1 ≤ x ≤ (p − 1)/2 ⟺ 1 ≤ x^{∗} ≤ (p − 1)/2

and similarly for y. This transformation interchanges A and B:

(x, y) ∈ A ⟺ y > \frac{qx}{p} + \frac{1}{2}
⟺ \frac{q + 1}{2} − y^{∗} > \frac{q}{p} (\frac{p + 1}{2} − x^{∗}) + \frac{1}{2}
⟺ x^{∗} > \frac{p}{q}y^{∗} + \frac{1}{2}
⟺ (x^{∗}, y^{∗}) ∈ B.

(ii) We count the lattice points in C_{1}. For 1 ≤ x ≤ (p − 1)/2:

(x, y) ∈ C_{1} ⟺ \frac{qx}{p} < y < \frac{qx}{p} + \frac{1}{2}.

(Equality is impossible for lattice points). For each x, there is at most one y satisfying this, and

Such a y exists ⟺ \frac{qx}{p} < ⌊\frac{qx}{p} + \frac{1}{2}⌋
⟺ ⌊\frac{qx}{p}⌋ < \frac{qx}{p} < ⌊\frac{qx}{p} + \frac{1}{2}⌋
⟺ ⌊\frac{qx}{p}⌋ + \frac{1}{2} < \frac{qx}{p} < ⌊\frac{qx}{p}⌋ + 1
⟺ \frac{1}{2} < \frac{qx}{p} − ⌊\frac{qx}{p}⌋ < 1
⟺ \frac{p}{2} < qx − p ⌊\frac{qx}{p}⌋ < p
⟺ the least residue of qx mod p is negative.

By Gauss’ Lemma, if s_{1} is the number of x for which this occurs, then

(\frac{q}{p}) = (−1)^{s_{1}}

as claimed.

(iii) is similar to (ii). □

Nigel Byott December 2002