MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

The sign of the quadratic Gauss sum $\tau$ can be obtained from the spectrum of the discrete Fourier transform $\Phi$: the trace of $\Phi$ gives $\tau$, and $\det\Phi$ distinguishes $\tau$ from $-\tau$.
Recall that for an odd prime $p$ the quadratic Gauss sum can be defined by $$\tau = \sum_{n=0}^{p-1} \zeta^{n^2}$$ where $\zeta = e^{2\pi i / p}$. It is elementary that $|\tau|^2 = p$ and that $\tau$ is real or pure imaginary according as $p \equiv 1 \bmod 4$ or $p \equiv -1 \bmod 4$. In fact $\tau$ is always $+\sqrt p$ in the former case, and $+i\sqrt p$ in the latter, but this is notoriously tricky to prove.
One trick is to recognize $\tau$ as the trace of the discrete Fourier transform on ${\bf C}^p$, which has matrix $$\Phi = (\zeta^{mn})_{m,n=0}^{p-1}.$$ Now $\Phi^2$ is the matrix whose $(m,n)$ entry is $p$ if $m+n \equiv 0 \bmod p$ and $0$ otherwise (this is tantamount to discrete Fourier inversion). This matrix has eiganvalues $+1$ and $-1$ with multiplicity $(p+1)/2$ and $(p-1)/2$ respectively. Hence $\Phi$ has eigenvalues $i^k \sqrt p$ ($k=0,1,2,3$) with multiplicities $m_k$ satisfying $m_0 + m_2 = (p+1)/2$ and $m_1 + m_3 = (p-1)/2$, and then $\tau = \sum_{k=0}^3 m_k i^k \sqrt p$. Since we already know $\tau$ up to sign there are only two possibilities: if $p \equiv 1 \bmod 4$ then $m_0$ or $m_2$ is $(p+3)/4$ and the other three $m_k$ are $(p-1)/4$, while if $p \equiv -1 \bmod 4$ then $m_1$ or $m_3$ is $(p-3)/4$ and the other three $m_k$ are $(p+1)/4$. We are to show that the odd man out is always $m_0$ in the former case and $m_3$ in the latter.
In each case we can decide the correct choice by computing the sign (a.k.a. argument) of $\det \Phi = p^{p/2} \prod_{k=0}^3 i^{k m_k}$. We can do this because $\Phi$ is a Vandermonde matrix, whence $\det\Phi$ has the product expansion $\prod_{0 \leq m < n < p} (\zeta^n - \zeta^m)$. Each factor $\zeta^n - \zeta^m$ is a positive real multiple of $\exp((m+n+\frac12)\pi i)$. It soon follows that $\det\Phi = i^{(1-p)/2} p^{p/2}$ (we already knew $\left|\det\Phi\right|$ because each eigenvalue has absolute value $\sqrt{p}$), and conclude as desired that $\tau = \sqrt{p}$ when $p \equiv 1 \bmod 4$ while $\tau = i\sqrt{p}$ when $p \equiv -1 \bmod 4$.