# 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 $n$th 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