QUADRATIC RECIPROCITY VIA LINEAR ALGEBRA

M. RAM MURTY

Abstract. We adapt a method of Schur to determine the sign in the quadratic Gauss sum and derive from this, the law of quadratic reciprocity.

1. Introduction

Let p and q be odd primes, with p ≠ q. We define the Legendre symbol (p/q) to be 1 if p is a square modulo q and −1 otherwise. The law of quadratic reciprocity, first proved by Gauss in 1801, states that

(p/q)(q/p) = (−1)^{(p−1)(q−1)/4}.

It reveals the amazing fact that the solvability of the congruence x^{2} ≡ p(mod q) is equivalent to the solvability of x^{2} ≡ q(mod p).

There are many proofs of this law in the literature. Gauss himself published five in his lifetime. But all of them hinge on properties of certain trigonometric sums, now called Gauss sums, and this usually requires substantial background on the part of the reader. We present below a proof, essentially due to Schur [2] that uses only basic notions from linear algebra. We say “essentially” because Schur’s goal was to deduce the sign in the quadratic Gauss sum by studying the matrix

A = (ζ^{rs}) 0 ≤ r ≤ n − 1, 0 ≤ s ≤ n − 1

where ζ = e^{2πi/n}. For the case of n = p a prime, Schur’s proof is reproduced in [1] and a ‘slicker’ proof was later supplied by Waterhouse [3]. Our point is to show that Schur’s proof can be modified to determine tr A when n is an odd number and this allows us to deduce the law of quadratic reciprocity.

2. The trace of A

Observe that the (u, v)-th entry of A^{2} is

∑_{k=0}^{n−1} ζ^{uk}ζ^{kv} = \{ \begin{matrix}n & if u + v ≡ 0(mod n) \\ 0 & otherwise \end{matrix}

so that

A^{2} = (\begin{matrix}n & 0 & ⋯ & 0 & 0 \\ 0 & 0 & ⋯ & 0 & n \\ 0 & 0 & ⋯ & n & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & ⋯ \\ 0 & n & ⋯ & 0 & 0 \end{matrix}) .

1991 Mathematics Subject Classification. Primary: 11A15, Secondary: 11L05.

Key words and phrases. quadratic reciprocity, Gauss sums .

It is easily seen that A^{4} = n^{2}I, from which we deduce that the eigenvalues of A^{2} are ±n. For each eigenvalue, we can compute the eigenspace directly. For example, for the eigenvalue n, we get that any eigenvector (x_{0}, x_{1}, ⋯ x_{n−1}) must satisfy the system of equations x_{n−j} = x_{j}, 1 ≤ j ≤ n − 1. For n odd, we find the dimension of this eigenspace to be 1 + (n − 1)/2 = (n + 1)/2. Similarly, the eigenspace corresponding to −n has dimension (n − 1)/2. Therefore the characteristic polynomial of A^{2} is

(x − n)^{(n+1)/2}(x + n)^{(n−1)/2}.

We conclude that the eigenvalues of A are ±\sqrt{n}, ±i\sqrt{n}, where i = \sqrt{−1}. Let a, b, c, d denote the multiplicities of the eigenvalues \sqrt{n}, −\sqrt{n}, i\sqrt{n} and −i\sqrt{n} respectively. Then

a + b = \frac{n + 1}{2}; c + d = \frac{n − 1}{2}  (2.1)

so that

tr A = ((a − b) + (c − d)i) \sqrt{n}.  (2.2)

On the other hand,

|tr A|^{2} = ∑_{k,ℓ} ζ^{k^{2}−ℓ^{2}} = ∑_{k,ℓ} ζ^{(k−ℓ)(k+ℓ)}.

Setting k − ℓ = α in the sum, we obtain

|tr A|^{2} = ∑_{α,ℓ} ζ^{α^{2}+2αℓ}.

Since n is odd, the inner sum for α fixed is zero unless α ≡ 0(mod n) in which case it is n. We have proved:

Lemma 2.1. For odd n,

|tr A| = \sqrt{n}.

Corollary 1.

tr A = \{ \begin{matrix}±\sqrt{n} & if n ≡ 1(mod 4) \\ ±i\sqrt{n} & if n ≡ 3(mod 4) \end{matrix}

Proof. From (2.2),

|tr A|^{2} = ((a − b)^{2} + (c − d)^{2}) n

and we deduce c − d = 0 and a − b = ±1 or a − b = 0 and c − d = ±1. In the first case using (2.1), we solve the system a + b = (n + 1)/2, a − b = ±1 and deduce n ≡ 1(mod 4). Similarly, in the second case, we deduce n ≡ 3(mod 4). This proves the corollary.

3. The determinant of A

Recall the Vandermonde determinant:

|\begin{matrix}1 & x_{1} & x_{1}^{2} & ⋯ & x_{1}^{n−1} \\ 1 & x_{2} & x_{2}^{2} & ⋯ & x_{2}^{n−1} \\ & & & ⋯ \\ 1 & x_{n} & x_{n}^{2} & ⋯ & x_{n}^{n−1} \end{matrix}| = ∏_{i<j}(x_{j} − x_{i}).

Now det A is a Vandermonde determinant. It is somewhat easier to consider (det A)^{2}:

(det A)^{2} = (−1)^{\binom{n}{2}} ∏_{r≠s}(ζ^{r} − ζ^{s}).

The product is equal to

∏_{j=0}^{n−1} f′(ζ^{j})

with f(x) = x^{n} − 1. Thus,

(det A)^{2} = (−1)^{\binom{n}{2}}n^{n},

from which we deduce

det A = ±i^{\binom{n}{2}}n^{n/2}.  (3.1)

We would like to determine the sign in (3.1). This is easily done as in [2]. We have

det A = ∏_{s<r}(ζ^{r} − ζ^{s}) = ∏_{s<r} η^{r+s}(η^{(r−s)} − η^{−(r−s)})

where η = e^{πi/n}. Since

∑_{s<r}(r + s) = ∑_{r=1}^{n−1} ∑_{s=0}^{r−1}(r + s) = ∑_{r=1}^{n−1} (r^{2} + \frac{r(r − 1)}{2}) = 2n (\frac{n − 1}{2})^{2}

is divisible by 2n, we deduce

det A = ∏_{s<r} (2i sin \frac{(r − s)π}{n} ) = i^{\binom{n}{2}}(positive quantity).

Thus, from 3.1 we conclude

Lemma 3.1. For n odd,

det A = i^{\binom{n}{2}}n^{n/2}.

Corollary 2. For n odd,

2b + c − d ≡ \binom{n}{2} (mod 4).

Proof. Since det A is the product of the eigenvalues

det A = (\sqrt{n})^{a}(−\sqrt{n})^{b}(i\sqrt{n})^{c}(−i\sqrt{n})^{d} = (−1)^{b+d}i^{c+d}n^{n/2} = i^{2b+c+3d}n^{n/2}.

Thus, by Lemma 3.1,

2b + c + 3d ≡ 2b + c − d ≡ \binom{n}{2} (mod 4),

from which the result follows.

Corollary 2 can be used to determine tr A explicitly. Returning to case 1, c − d = 0 so that

2b ≡ \binom{n}{2} (mod 4).

Thus from (2.1),

a − b = a + b − 2b = \frac{n + 1}{2} − 2b ≡ \frac{n + 1}{2} − \frac{n(n − 1)}{2} ≡ 1(mod 4)

because n ≡ 1(mod 4). Similarly in the second case, a − b = 0 so that from (2.1) 2b = (n + 1)/2 and

c − d ≡ \frac{n(n − 1)}{2} + 2b ≡ −\frac{n − 1}{2} + \frac{n + 1}{2} ≡ 1(mod 4).

This proves:

Theorem 1. For odd n,

tr A = ∑_{j=0}^{n−1} e^{2πij^{2}/n} \{ \begin{matrix}\sqrt{n} & if n ≡ 1(mod 4) \\ i\sqrt{n} & if n ≡ 3(mod 4). \end{matrix}

4. The law of quadratic reciprocity

Let

S(n, a) = ∑_{j=0}^{n−1} e^{2πij^{2}a/n}.

We will prove:

Lemma 4.1. Let m, n be coprime positive integers. Then

S(m, n)S(n, m) = S(mn, 1).

Proof. We have

∑_{j=0}^{n−1} ∑_{k=0}^{m−1} e^{2πij^{2}m/n}e^{2πik^{2}n/m} = ∑_{j,k} e^{\frac{2πi}{mn} (j^{2}m^{2}+k^{2}n^{2})} = ∑_{j,k} e^{\frac{2πi}{mn} (jm+kn)^{2}}

We note that as 0 ≤ j ≤ n−1 and 0 ≤ k ≤ m−1, the set of integers jm+kn forms a complete set of residue classes modulo mn. The result is now immediate.

If p, q are primes, note that

∑_{j=0}^{p−1} e^{2πij^{2}q/p} = ∑_{k=0}^{p−1} (1 + (\frac{k}{p} )) e^{2πikq/p} = ∑_{k=0}^{p−1} (\frac{k}{p} ) e^{2πikq/p}

because the sum of the p-th roots of unity is zero. Also, the right hand side is equal to

(\frac{q}{p}) ∑_{k=0}^{p−1} (\frac{kq}{p} ) e^{2πikq/p} = (\frac{q}{p}) S(p, 1)

by the multiplicative property of the Legendre symbol. Therefore, S(p, q) = (q/p)S(p, 1). We can now deduce

Theorem 2.

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

for any distinct odd primes p, q.

Proof. Define for odd n, e(n) = 1 if n ≡ 1(mod 4) and i if n ≡ 3(mod 4). Then, the result of Theorem 1 can be written as S(n, 1) = e(n)\sqrt{n}. Thus,

e(pq)\sqrt{pq} = S(pq, 1) = S(p, q)S(q, p) = (q/p)(p/q)S(p, 1)S(q, 1) = (q/p)(p/q)e(p)e(q)\sqrt{pq}

from which we deduce

(q/p)(p/q)e(p)e(q) = e(pq)

which is the law of quadratic reciprocity.

References

[1] Z. Borevich and I. Shafarevich, Number Theory, translated by Newcomb Greenleaf, Academic Press, New York, 1966.

[2] I. Schur, Über die Gausschen Summen, Nachrichten von der Königlichen Gessellschaft zu Göttingen, Mathematisch - Physikalische Klass, (1921), 147-153.

[3] W.C. Waterhouse, The sign of the Gaussian sum, Journal of Number Theory, 2 (1970), 363.

Department of Mathematics and Statistics, Queen’s University, Kingston, ON, Canada, K7L 3N6.

E-mail address: murty@mast.queensu.ca