A multiplicative property of quadratic Gauss sums

Quadratic Gauss sums were first formulated and studied by Carl Friedrich Gauss himself, motivated partly by his desire to prove the law of quadratic reciprocity in different ways. They are sums of the form

G(m; n) = \sum_{r=1}^n w^{mr^2}
where
w = e^{2\pi i/n}
They are called quadratic Gauss sums because under certain circumstances they can be expressed in terms of Legendre symbols, which are quadratic characters modulo a prime number. I will explore some properties of Gauss sums associated with Dirichlet characters in a later note. In this short note I want to record a proof I have worked out of a multiplicative property of quadratic Gauss sums which says that
G(m; n) \cdot G(n; m) = G(1; mn)     (1)
when gcd(m, n) = 1. A standard way to prove this in the literature is to begin by proving a more general multiplicative property which says
G(m; na) \cdot G(n; ma) = G(a; mn)
when gcd(m, n) = 1 and gcd(a, mn) = 1. One then obtains the previous result by setting a = 1. I found it instructive to go through the process of proving (1) directly, however, without going through the general case first, and I want to record the steps involved in doing this here. I’ll also give an illustrative example of (1) at the end.

It is necessary to prove two results first, and then these can be used to prove (1).

Result 1: We can write G(m; n) = \sum w^{mr^2} where the summation is taken over any complete set of residues mod n, because w^{mr^2} = w^{ms^2} whenever r \equiv s (mod n).
Proof: If r \equiv s (mod n) then r = kn + s for some integer k, so
w^{mr^2} = w^{m(k^2n^2+ 2kns + s^2)}
= (w^n)^{m(k^2n+2ks)}\cdot w^{ms^2}
= w^{ms^2}
since w is an nth root of unity.
Any set of n integers is a complete set of residues modulo n provided no two of them are congruent modulo n. Each integer in a complete set of residues modulo n will be congruent to one, and only one, integer in the set \{1, 2, \ldots, n\}. By the result obtained above, therefore, it makes no difference whether we sum over the integers 1, 2, \dots, n, or over the integers in any complete set of residues modulo n. Therefore
G(m; n) = \sum w^{mr^2}
where the summation extends over any complete set of residues, as claimed. QED

Result 2: Let m and n be integers such that gcd(m, n) = 1 and let r and s run through complete sets of residues mod m and n respectively. Then t = nr + ms runs through a complete set of residues mod mn and
t^2 = n^2r^2 + m^2s^2 (mod mn)
Proof: Let
R = \{r_1, r_2, \ldots, r_m\}
be a complete set of residues mod m, and let
S = \{s_1, s_2, \dots, s_n\}
be a complete set of residues mod n. Let
t_{ij} = nr_i + ms_j
where i = 1, \ldots, m, j = 1, \dots, n. Then the set
T = \{t_{11}, t_{12}, \ldots, t_{1n}, t_{21}, t_{22}, \ldots, t_{2n}, \ldots, t_{m1}, t_{m2}, \ldots, t_{mn}\}
contains mn elements corresponding to the mn possible different ways of combining an element from R with an element from S. The claim to be proved is then that the set T is a complete set of residues mod mn.
To see this, suppose t_{ij} and t_{pq} are two distinct elements from T, and suppose they are congruent mod mn. I will show that this leads to a contradiction. We have
t_{ij} \equiv t_{pq} (mod mn)
\Longleftrightarrow  nr_i + ms_j \equiv nr_p + ms_q (mod mn)
\Rightarrow n(r_i - r_p) \equiv m(s_q - s_j)  (mod mn)
\Rightarrow n(r_i - r_p) \equiv m(s_q - s_j) \equiv 0  (mod m)
and m(s_q - s_j) \equiv n(r_i - r_p) \equiv 0  (mod n)
(since gcd(m, n) = 1). These last two congruences imply
r_i \equiv r_p (mod m) and s_q \equiv s_j (mod n)
which cannot both be true since t_{ij} and t_{pq} are distinct elements of T and so at least one of the pairs r_i, r_p and s_q, s_j must consist of distinct elements from the corresponding complete set of residues mod m or n respectively. This is a contradiction, so it follows that any two distinct elements of T must be incongruent, so T is a complete set of residues mod mn.
We have
t^2 = (nr + ms)^2 = n^2r^2 + m^2s^2 + 2mnrs \equiv n^2r^2 + m^2s^2  (mod mn)
as claimed. QED

We can now use these two results to prove the multiplicative property in (1) above. By Result 1, we can sum over any complete sets of residues. Therefore using the sets R, S and T as defined in Result 2, we have
G(m; n) = \sum_{s \in S}w^{ms^2}
G(n; m) = \sum_{r \in R}w^{nr^2}
G(1; mn) = \sum_{t \in T}w^{t^2}
Therefore
G(m; n)G(n; m) = \sum_{s \in S}w^{ms^2}\sum_{r \in R}w^{nr^2}
= \sum_{\substack{s \in S \\ r \in R}}w^{nr^2+ms^2}
= \sum_{t \in T}w^{t^2}
= G(1; mn)
where the penultimate equality follows from the fact that
nr^2 + ms^2 \equiv t^2 (mod mn) as is clear from the expression for t^2 in Result 2. QED

Example: Evaluating each term of the equation G(m; n)G(n; m) = G(1; mn) when m = 3 and n = 4 we get

G(3; 4) = \sum_{r=1}^4w^{3r^2} = \sum_{r=1}^4e^{3\pi ir^2/2}
= e^{3\pi i/2} + e^{6\pi} + e^{3\pi i/2} + e^{24\pi}
= -i + 1 - i + 1 = 2(1 - i)

G(4; 3) = \sum_{r=1}^3w^{4r^2} = \sum_{r=1}^3e^{2\pi ir^2/3}
= e^{2\pi i/3} + e^{2\pi i/3} + e^{6\pi i}
= -\frac{1}{2} + \frac{\sqrt{3}}{2}i - \frac{1}{2} + \frac{\sqrt{3}}{2}i + 1 = \sqrt{3}i

G(1; 12) = \sum_{r=1}^{12}w^{r^2} = \sum_{r=1}^{12}e^{\pi ir^2/6}
= e^{\pi i/6} + e^{2\pi i/3} + e^{3\pi i/2} + e^{2\pi i/3} + e^{\pi i/6} + e^{6\pi i}
+ e^{\pi i/6} + e^{2\pi i/3} + e^{3\pi i/2} + e^{2\pi i/3} + e^{\pi i/6} + e^{24\pi i}
= 2\sqrt{3}(1+i)

and so G(3; 4)G(4; 3) = G(1; 12). END