# How to discover how to evaluate the Gauss sum?

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?

-
The answer below is correct. Historically, I suspect this argument was not the first argument - rather a more complicated computation was probably used. At some point, the concept of a discrete Fourier transform was discovered, and people realized that this sort of sum could be best understood as examples of that phenomenon. This sort of proof, then, seems like a bit of "magic," because it is hiding the general rules about discrete FT in a specific proof. –  Thomas Andrews Apr 16 '11 at 16:59
You might also try to calculate the sum directly, when $p=3,5,7,\ldots$. Such experiments often, but not always, lead to a "light-bulb experience". –  Jyrki Lahtonen May 28 '12 at 15:41

perhaps it is an answer to your question: $a\mapsto g_p(a)$ is the (discrete) Fourier transform of $n\mapsto (\frac{n}{p})$ (which is a function on the abelian group $\mathbb{Z}/p\mathbb{Z}$ and the dual group is again $\mathbb{Z}/p\mathbb{Z}$). $\sum_a g_p(a) g_p(-a)=\sum_a |g_p(a)|^2$ is then $p\sum_n (\frac{n}{p})^2=p(p-1)$ by Plancherel's formula.