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.

  • $\begingroup$ 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.$ $\endgroup$ – 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}}. $$

  • $\begingroup$ How do I formally turn the double summation into a single one? $\endgroup$ – Joshhh Jul 19 '16 at 10:06
  • $\begingroup$ @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)}$ $\endgroup$ – reuns Jul 19 '16 at 10:20
  • $\begingroup$ How does $\left(\frac{c}{pq}\right)$ have a meaning as a Legendre symbol? $\endgroup$ – Joshhh Jul 19 '16 at 10:23
  • $\begingroup$ @Joshhh yes it is named the Jacobi symbol. $\endgroup$ – reuns Jul 19 '16 at 10:27
  • $\begingroup$ @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$ $\endgroup$ – reuns Jul 19 '16 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.