If $\chi$ is a real non-trivial primitive character modulo $q\ge 1$, then how could one show that $\sum_{n\in \mathbb Z/q\mathbb Z} \chi(n)e\left(\frac nq\right) = \sum_{n\in \mathbb Z/q\mathbb Z} e\left(\frac {n^2}q\right) $ where $e(z) = \exp(2\pi i z)$? I think one should be able to see this directly, but I simply cannot figure out anything useful. If $n$ is a square mod $q$, then of course $\chi(n) = 1$, so maybe that would be a good place to start... But I've been stuck for quite some time on this.
Some help would be greatly appreciated. Thank you.