Prove that $\sum _{x=0}^{p-1}e^{\frac {2\pi ix^{2}}{p}}={\sqrt {p}} $ , $ p \equiv 1{\pmod {4}}$ 
Prove that :
$$\sum _{x=0}^{p-1}e^{\frac {2\pi ix^{2}}{p}}={\begin{cases}{\sqrt {p}}&{\text{if}}\ p\equiv 1{\pmod {4}}\\i{\sqrt {p}}&{\text{if}}\ p\equiv 3{\pmod {4}}\end{cases}}$$ where $p$ is a prime number

Can someone give me hints for this, I am completely stuck in this problem.
This was given in my roots of unity handout.
I first, took $S=\sum _{x=0}^{p-1}e^{\frac {2\pi ix^{2}}{p}}$.
The handout asked me to prove $|S|=\sqrt p$, but I am not able to proceed.
Thanks in advance!
 A: Oh boy! This made me struggle a bit XD. All I could do, was to prove $|S|=\sqrt{p}$ as the handout suggests you to!
First of all, lets re-write the sum $S$. We will denote $\zeta := e^{2\pi i/p}$ and $(a|p)$ denotes the Legendre symbol which is defined as
$$(a|p):=\begin{cases}1 & \text{if $a$ is a quadratic residue $\pmod{p}$}\\-1 & \text{if $a$ is a quadratic non residue $\pmod{p}$}\\0 &\text{if $p|a$}\end{cases}$$

We claim that
$$S:=\sum_{x=0}^{p-1}\zeta^{x^2}=\sum_{x=0}^{p-1}(x|p)\zeta^{x}$$

The above claim is obviously gonna help us to deal with the $x^2$ in the exponent. For the proof of the claim, we note that we have
$$\sum_{x=0}^{p-1}\zeta^x=0\tag*{(sum of all $p^{th}$ roots of unity is $0$)}$$
\begin{align}\implies &1+\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x +\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}\zeta^x=0\\\implies & 1+\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x=\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}-\zeta^x\\ \implies & 1 +2\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x = \sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x+\sum_{\substack{x=1\\(x|p)=-1}}^{p-1}-\zeta^x = \sum_{x=0}^{p-1}(x|p)\zeta^x\tag*{(1)}\\\end{align}and as number of quadratic residues is $(p-1)/2$, we get,
$$1+2\sum_{\substack{x=1\\(x|p)=1}}^{p-1}\zeta^x = 1+ \sum_{x=1}^{p-1}\zeta^{x^2}=\sum_{x=0}^{p-1}\zeta^{x^2}$$and thus, from $(1)$, we complete the proof of our claim.
Now, to show $|S|=\sqrt{p}$, we first investigate $S^2$. For that, note that,
$$(-1|p)\sum_{x=0}^{p-1}(x|p)\zeta^{x}=\sum_{x=0}^{p-1}(x|p)\zeta^{-x}$$and so,$$\begin{align} (-1|p)S^2&= \left(\sum_{n=0}^{p-1}(n|p)\zeta^{n}\right)\left(\sum_{m=0}^{p-1}(m|p)\zeta^{-m}\right)\\ &=\sum_{n=0}^{p-1}\sum_{m=0}^{p-1} (n|p)(m|p)\zeta^{n-m}\\ &=\sum_{n=0}^{p-1}\sum_{m=0}^{p-1} (mn|p)\zeta^{n-m}\\ & =\sum_{d=0}^{p-1}\zeta^d \sum_{n=0}^{p-1}(n(n+d)|p)
\end{align}$$and clearly, if $d\neq 0$, then the inner sum is just $-1$ and when $d=0$, the inner sum is $p-1$. Thus,
$$(-1|p)S^2=(p-1)-\sum_{l=1}^{p-1}\zeta^l=p\implies S^2=(-1|p)p=(-1)^{(p-1)/2}p$$and thus, $$\boxed{\left(\sum_{x=0}^{p-1}e^{\frac{2\pi i x^2}{p}}\right)^2=\begin{cases}p &\text{if $p\equiv_4 1$}\\ -p &\text{if $p\equiv_4 3$}\end{cases}}\tag*{$\blacksquare$}$$
