If $p$ is prime and $S = \sum_{j=0}^{p-1} {\varepsilon}^{j^2}$, where $\varepsilon$ is a primitive $p$th root of unity, what is $S^2$?
What I did so far is write $S^2 = \sum_{0 \le a,b \le p-1} {\varepsilon}^{a^2+b^2}$, and I checked small cases. I found that for $p\equiv 1\pmod 4$, $$S^2 = (2p-1)\varepsilon^0+(p-1)({\varepsilon}^1+...+{\varepsilon}^{p-1}) = p,$$ and for $p\equiv -1\pmod 4$, $$S^2 = \varepsilon^0+(p+1)({\varepsilon}^1+...+{\varepsilon}^{p-1}) = -p,$$ so it seems that $$S^2 = {(-1)}^{\frac{p-1}{2}}\cdot p.$$
So essentially I turned it into a number theory problem, where we have to show that if we add all possible ordered pairs of squares from $0^2$ to ${(p-1)}^2$ mod $p$, we will get every remainder the same number of times (aside from $0$). I was also able to show that the number of $\varepsilon^0$ terms is correct, using the fact that there are always $\frac{p-1}{2}$ remainder classes mod $p$, and $-1$ is a quadratic residue iff $p\equiv 1\pmod 4$.
And that's where I got stuck, I am not sure how to attack this question. Any tips on where to go from here, or alternate approaches are welcome.