# Product of Gauss sums $\tau_p,\tau_q$

Let $p,q$ be different odd primes, and let $\tau_p = \sum\limits_{a=1}^{p}\left(\frac{a}{p}\right)e^{\frac{2\pi ia}{p}}$, $\tau_p = \sum\limits_{b=1}^{q}\left(\frac{b}{q}\right)e^{\frac{2\pi ib}{q}}$. I need to prove that $$(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\tau_p\tau_q = \sum\limits_{c=1}^{pq}\left(\frac{c}{p}\right)\left(\frac{c}{q}\right)e^{\frac{2\pi ic}{pq}}$$

So, we have that $$\tau_p\tau_q = \sum\limits_{a=1}^{p}\sum\limits_{b=1}^q\left(\frac{a}{p}\right)\left(\frac{b}{q}\right)e^{\frac{2\pi i(aq+bp)}{pq}}$$

If we use quadratic reciprocity, we get that $$(-1)^{\frac{p-1}{2}\frac{q-1}{2}}\tau_p\tau_q = \sum\limits_{a=1}^p\sum\limits_{b=1}^q\left(\frac{aq}{p}\right)\left(\frac{bp}{q}\right)e^{\frac{2\pi i(aq+bp)}{pq}}$$ This immediately implies that a definition $c = aq+bp$ is required. But, I can't seem to work out the index swap that will allow me to change from a double summation to a single summation. I've tried to prove that every $c\mod pq$ has a single decomposition of $aq + bp\mod pq$, where $1\leq a\leq p, 1\leq b\leq q$. But I was only able to prove uniqueness (using the Chinese remainder theorem). Also, I don't see how this helps me.

• If you have uniqueness, then notice that both have $pq$ many, so that every $c\pmod {pq}$ can be uniquely written as $ap+bq\pmod{pq}$ for some $1\le a\le p,\ 1\le b\le q.$ – awllower Jul 19 '16 at 16:17

By the Chinese Remainder Theorem the quantity $c=aq+bp$ ranges over all the residue classes modulo $pq$, when $a$ ranges over residue classes modulo $p$ and $b$ over residule classes modulo $q$. Also observe that $$\left(\frac c p\right)=\left(\frac {aq+bp}p\right)=\left(\frac{aq}p\right)$$ because $c\equiv aq\pmod p$. Similarly $$\left(\frac c q\right)=\left(\frac {bp}q\right).$$ Therefore $$\sum\limits_{a=1}^p\sum\limits_{b=1}^q\left(\frac{aq}{p}\right)\left(\frac{bp}{q}\right)e^{\frac{2\pi i(aq+bp)}{pq}} =\sum_{c=1}^{pq}\left(\frac cp\right)\left(\frac cq\right)e^{\frac{2\pi i c}{pq}}.$$
• @Joshhh he said that $\left(\frac{aq}{p}\right)\left(\frac{bp}{q}\right) = \left(\frac {aq+bp}p\right)\left(\frac {aq+bp}q\right)= \left(\frac {aq+bp}{pq}\right)$ so your double sum becomes $\sum_{c=1}^{pq} \left(\frac {c}{pq}\right) e^{2 i \pi c / (pq)}$ – reuns Jul 19 '16 at 10:20
• How does $\left(\frac{c}{pq}\right)$ have a meaning as a Legendre symbol? – Joshhh Jul 19 '16 at 10:23
• @Joshhh anyway the trick of the Gauss sum is that $\sum_{a=1}^p \left(\frac{aq}{p}\right) e^{2 i \pi aq/p} = \sum_{a=1}^p \left(\frac{a}{p}\right) e^{2 i \pi a/p}$ whenever $q$ is inversible modulo $p$ – reuns Jul 19 '16 at 10:33