Advanced Number Theory Note #16: A proof of the law of quadratic reciprocity using Gauss sums and quadratic characters

Gauss The prince of mathematicians (princeps mathematicorum), Carl Friedrich Gauss, arguably the greatest mathematician who ever lived, devoted a lot of attention to exploring alternative proofs of the law of quadratic reciprocity. As I mentioned in a previous note, this is actually a very deep result which has had a profound impact on modern mathematics. A rather good Wikipedia page about the quadratic reciprocity law has a section entitled connection with cyclotomy which makes clear its importance to the development of modern class field theory, and a history and alternative statements section catalogues its somewhat convoluted history.

In the present note I want to explore in detail one of the (many) approaches to proving the law of quadratic reciprocity, an approach which uses Gauss sums and Legendre symbols. (In a later note I will explore another proof using quadratic Gauss sums which involves contour integration techniques from complex analysis).

The proof consists of three key theorems, as follows:

Theorem I. This proves that G(1, \chi)^2 = (-1|p)p when \chi = (r|p).

Theorem II. This proves that G(1, \chi)^{q-1} \equiv (q|p) (mod q) is equivalent to the law of quadratic reciprocity, using Theorem I.

Theorem III. This proves an identity for G(1, \chi)^{q-1} from which the congruence in Theorem II follows, thus completing the overall proof of the quadratic reciprocity law.

In a previous note I stated a version of the law of quadratic reciprocity due to Legendre as follows: if p and q are distinct odd primes then

(p|q) = \begin{cases} (q|p),& \text{if either } p \equiv 1 \ \text{(mod 4) } \text{or } q \equiv 1 \ \text{(mod 4)}\\ -(q|p), & \text{if } p \equiv q \equiv 3 \ \text{(mod 4)} \end{cases}

For the purposes of the proof in the present note it is necessary to express the quadratic reciprocity law as

(q|p) = (-1)^{(p - 1)(q - 1)/4}(p|q)

These two formulations are completely equivalent. To see this, note that if p \equiv 1 (mod 4) or p \equiv 1 (mod 4), the exponent on (-1) in the second formulation reduces to an even integer so we get (q|p) = (p|q). On the other hand, if p \equiv q \equiv 3 (mod 4), the exponent on (-1) in the second formulation reduces to an odd integer, so we get (q|p) = -(p|q).

Also note that the proof makes use of Gauss sums incorporating the Legendre symbol as the Dirichlet character in the summand, i.e., Gauss sums of the form

G(n, \chi) = \sum_{r \text{mod } p} \chi(r) e^{2 \pi i n r/p}

where \chi(r) = (r|p), and the Legendre symbol in this context is referred to as the quadratic character mod p. Since the modulus is prime, the Dirichlet character here is primitive and we have that G(n, \chi) is separable with

G(n, \chi) = \overline{\chi(n)} G(1, \chi) = (n|p) G(1, \chi)

for every n, because either gcd(n, p) = 1, or if gcd(n, p) > 1 we must have p|n in which case G(n, \chi) = 0 because e^{2 \pi i n r/p} = 1 and \sum_{r \text{mod } p} \chi(r) = 0 (for non-principal characters the rows of the character tables sum to zero).

Theorem I. If p is an odd prime and \chi(r) = (r|p) then

G(1, \chi)^2 = (-1|p) p

Proof: We have

G(1, \chi) = \sum_{r = 1}^{p - 1} (r|p) e^{2 \pi i r/p}

and therefore

G(1, \chi)^2 = \sum_{r = 1}^{p - 1} (r|p) e^{2 \pi i r/p} \times \sum_{s = 1}^{p - 1} (s|p) e^{2 \pi i s/p}

= \sum_{r = 1}^{p - 1} \sum_{s = 1}^{p - 1} (r|p) (s|p) e^{2 \pi i (r + s)/p}

For each pair of values of r and s there is a unique t mod p such that

s \equiv tr (mod p)

since this is a linear congruence with a unique solution. We also have that

(r|p) (s|p) = (r|p) (tr|p)

= (r|p) (r|p) (t|p)

= (r^2|p) (t|p)

= (t|p)

Therefore we can write

G(1, \chi)^2 = \sum_{r = 1}^{p - 1} \sum_{tr = 1}^{p - 1} (t|p) e^{2 \pi i r (1 + t)/p}

= \sum_{r = 1}^{p - 1} \sum_{t = 1}^{p - 1} (t|p) e^{2 \pi i r (1 + t)/p}

(where the index in the second summation has been reduced to t since t will range through all the least positive residues of p independently of r)

= \sum_{t = 1}^{p - 1} (t|p) \sum_{r = 1}^{p - 1} e^{2 \pi i r (1 + t)/p}

The last sum on r is a geometric sum of the form

g(1 + t) = \sum_{r = 1}^{p - 1} x^r

where

x = e^{2 \pi i (1 + t)/p}

so we have

g(1 + t) = \begin{cases} \frac{x^p - x}{x - 1} & \text{if } x \neq 1\\ p - 1 & \text{if } x = 1 \end{cases}

But it must be the case that x^p = 1 (because x is a pth root of unity), and we also have that x = 1 if and only if p|(1 + t), so we can write

g(1 + t) = \begin{cases} -1 & \text{if } p \nmid (1 + t) \\ p - 1 & \text{if } p | (1 + t) \end{cases}

Therefore

G(1, \chi)^2 = - \sum_{t = 1}^{p - 2} (t|p) + (p - 1) (p - 1|p)

(because the only value of t for which p|(1 + t) is t = p - 1, so we can pull this out of the summation and then for this value of t the Legendre symbol (t|p) becomes (p - 1|p))

= - \sum_{t = 1}^{p - 2} (t|p) - (p - 1|p) + p(p - 1|p)

= - \sum_{t = 1}^{p - 1} (t|p) + p(p - 1|p)

= - \sum_{t = 1}^{p - 1} (t|p) + p(-1|p)

(since (p - 1|p) = (-1|p))

= (-1|p) p

(because \sum_{t = 1}^{p - 1} (t|p) = 0 since (t|p) is a Dirichlet character mod p and the rows of Dirichlet character tables sum to zero). \square

Since (-1|p) = \pm 1, Theorem I tells us that G(1, \chi)^2 is an integer and it then follows that

G(1, \chi)^{q - 1} = (G(1, \chi)^2)^{(q - 1)/2}

is also an integer for every odd q. It turns out that the law of quadratic reciprocity is intimately related to the value of the integer G(1, \chi)^{q - 1} mod q, which is what the next theorem shows.

Theorem II. Let p and q be distinct odd primes and let \chi be the quadratic character (i.e., the Legendre symbol) mod p. Then the quadratic reciprocity law

(q|p) = (-1)^{(p - 1)(q - 1)/4}(p|q)

is equivalent to the congruence

G(1, \chi)^{q - 1} \equiv (q|p) (mod q)

Proof: From the result proved in Theorem I we have that

G(1, \chi)^{q - 1} = (G(1, \chi)^2)^{(q - 1)/2}

= (-1|p)^{(q - 1)/2} p^{(q - 1)/2}

= (-1)^{(p - 1)(q - 1)/4} p^{(q - 1)/2}

where the last equality follows from property (e) of Legendre symbols in my previous note which implies

(-1|p) = (-1)^{(p - 1)/2}

By property (d) of Legendre symbols we also have

p^{(q - 1)/2} \equiv (p|q) (mod q)

so we can write

G(1, \chi)^{q - 1} \equiv (-1)^{(p - 1)(q - 1)/4} (p|q) = (q|p) (mod q)

where the last equality follows from the law of quadratic reciprocity.

Therefore if the law of quadratic reciprocity holds, then so does

G(1, \chi)^{q - 1} \equiv (q|p) (mod q)

and vice versa. \square

The last stage of the proof is now to deduce the congruence in Theorem II from an identity for G(1, \chi)^{q - 1} which is established in the next theorem.

Theorem III. If p and q are distinct odd primes and if \chi is the quadratic character (i.e., Legendre symbol) mod p, we have

G(1, \chi)^{q - 1} = (q|p) \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)

where the summation indices satisfy the restriction

r_1 + \cdots + r_q \equiv q (mod p)

Proof: It is easy to show that the Gauss sum G(n, \chi) is a periodic function of n with period p since

G(n + p, \chi) = \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m (n + p)/p}

= \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m n/p} e^{2 \pi i m}

= \sum_{m = 1}^{p} \chi(m) e^{2 \pi i m n/p} = G(n, \chi)

Since therefore

G(n, \chi)^q = G(n + p, \chi)^q

it follows that G(n, \chi)^q is also a periodic function of n with period p. Therefore we have a finite Fourier expansion

G(n, \chi)^q = \sum_{m \ mod \ p} a_q(m) e^{2 \pi i m n/p}

where the coefficients are given by

a_q(m) = \frac{1}{p} \sum_{n \ mod \ p} G(n, \chi)^q e^{-2 \pi i m n/p}

(see my previous note on finding the finite Fourier expansion of an arithmetical function). Simply from the general definition of G(n, \chi) (using Legendre symbols as Dirichlet characters) we have

G(n, \chi)^q = \sum_{r_1 mod \ p} (r_1|p) e^{2 \pi i n r_1/p} \cdots \sum_{r_q mod \ p} (r_q|p) e^{2 \pi i n r_q/p}

= \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) e^{2 \pi i n (r_1 + \cdots + r_q)/p}

so we can write the above Fourier expansion coefficients as

a_q(m) = \frac{1}{p} \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) \times \sum_{n \ mod \ p} e^{2 \pi i n (r_1 + \cdots + r_q - m)/p}

The sum on n is a geometric sum of the form

g(r_1 + \cdots + r_q - m) = \sum_{n = 0}^{p - 1} x^n

where

x = e^{2 \pi i (r_1 + \cdots + r_q - m)/p}

so we have

g(r_1 + \cdots + r_q - m) = \begin{cases} \frac{x^p - 1}{x - 1} & \text{if } x \neq 1\\ p & \text{if } x = 1 \end{cases}

= \begin{cases} 0 & \text{if } x \neq 1\\ p & \text{if } x = 1 \end{cases}

(since x^p = 1 because x is a pth root of unity). Therefore in the expression for a_q(m) the sum on n vanishes unless r_1 + \cdots + r_q \equiv m (mod p), in which case the sum is equal to p. Therefore we can write

a_q(m) = \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)

where the summation indices satisfy the restriction

r_1 + \cdots + r_q \equiv m (mod p)

Now we return to the original expression for a_q(m), namely

a_q(m) = \frac{1}{p} \sum_{n \ mod \ p} G(n, \chi)^q e^{-2 \pi i m n/p}

and use this to obtain a different expression for a_q(m). The separability of G(n, \chi) means that

G(n, \chi) = (n|p) G(1, \chi)

We also have the result for odd q that

(n|p)^q = (n^q|p) = (n^{q-1}|p) (n|p) = (n|p)

(since q - 1 is even). Therefore we find

a_q(m) = \frac{1}{p} G(1, \chi)^q \sum_{n \ mod \ p} (n|p) e^{-2 \pi i m n/p}

= \frac{1}{p} G(1, \chi)^q G(-m, \chi)

= \frac{1}{p} G(1, \chi)^q (m|p) G(-1, \chi)

= (m|p) G(1, \chi)^{q - 1}

where the last equality follows from the fact that

G(1, \chi) G(-1, \chi) = G(1, \chi) (-1|p) G(1, \chi)

= G(1, \chi)^2 (-1|p)

= (-1|p) p (-1|p)

= ((-1)^2|p) p

= p

Therefore

(m|p) a_q(m) = (m|p) (m|p) G(1, \chi)^{q - 1}

= (m^2|p) G(1, \chi)^{q - 1}

= G(1, \chi)^{q - 1}

Taking m = q and the previously obtained expression for a_q(m) we get the claimed result

G(1, \chi)^{q - 1} = (q|p) \sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p)

where the summation indices satisfy the restriction

r_1 + \cdots + r_q \equiv q (mod p). \square

We are now in a position to deduce the law of quadratic reciprocity from Theorems I, II and III. From the result obtained in Theorem II, it suffices to show that

\sum_{r_1 mod \ p} \cdots \sum_{r_q mod \ p} (r_1 \cdots r_q |p) \equiv 1 (mod q)

where the summation indices satisfy the restriction

r_1 + \cdots + r_q \equiv q (mod p)

i.e., every term (r_1 \cdots r_q |p) in the summand satisfies this restriction. One way in which this restriction is satisfied is when

r_j \equiv 1 (mod p)

for j = 1, \dots, q. In this case we have

(r_1 \cdots r_q |p) = (1|p) = 1

Every other possible way of satisfying the restriction involves

r_j \not \equiv r_k (mod p)

for some j \neq k. For each of these ways, every cyclic permutation of r_1, \ldots, r_q satisfying the restriction contributes the same summand (r_1 \cdots r_q |p). Therefore for each of these ways of satisfying the restriction, each summand appears q times and therefore contributes 0 modulo q to the sum. Therefore only the scenario r_j \equiv 1 (mod p) for j = 1, \dots, q yields a non-zero contribution, so the sum is 1 (mod q). This completes the proof of the law of quadratic reciprocity.

To clarify the last point, consider the following

Example: Take p = 5 and q = 3. Then the equations are

\sum_{r_1 \ mod \ 5} \sum_{r_2 \ mod \ 5} \sum_{r_3 \ mod \ 5} (r_1 r_2 r_3|5) \equiv 1 (mod 3)

where the summation indices satisfy the restriction

r_1 + r_2 + r_3 \equiv 3 (mod 5)

In the case when r_1 \equiv r_2 \equiv r_3 \equiv 1 (mod 5) we have

(r_1 r_2 r_3|5) \equiv (1|5) = 1

so the first equation is satisfied.

Suppose we consider any other way of satisfying the restriction, say

r_1 \equiv 1, r_2 \equiv 3, r_3 \equiv 4 (mod 5)

so that

r_1 + r_2 + r_3 \equiv 8 \equiv 3 (mod 5)

Then the cyclic permutations

r_1 \equiv 4, r_2 \equiv 1, r_3 \equiv 3 (mod 5)

and

r_1 \equiv 3, r_2 \equiv 4, r_3 \equiv 1 (mod 5)

will also satisfy the restriction, and these contribute a total of

3 (1 \cdot 3 \cdot 4|5) \equiv 0 (mod 3)

to the sum. Therefore only the first way of satisfying the restriction will contribute to the sum, so the sum must equal 1.