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

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 $p$th 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 $p$th 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.