Define the Gauss sum to be $g_p(a) = \sum_{n=0}^{p-1}\left(\frac{n}{p}\right)\zeta_p^{an}.$
We want to compute $g_p(1)^2$ (the answer is it equals $\pm p$ sign depending $p \pmod 4$). To do this you can evaluate the following:
$\sum_{a=0}^{p-1}g_p(a)g_p(-a).$
I am wondering how anyone could come up with that? I don't have any understanding why that sum would be easier to compute (except that after doing it, it wasn't too hard). Can anyone shed light on this? Are there other ways to evaluate the sum?
And is this related to how the double integral of $\exp(-x^2)$ is used to find the single integral?