How to directly show $S=\sum_{k=1}^{m}e^{2\pi ik^2/m}=\sqrt{m}$ Let $S=\sum_{k=1}^{m}e^{2\pi ik^2/m}$,if $m$ is odd,how to directly calculate the absolute value of $S=\sqrt{m}$.Don't use Gauss sum since here it says "it's easily shown"
My try is as follows:
$$ \begin{align}S^2&=\left(\sum_{k=1}^{m}e^{2\pi ik^2/m}\right)\left(\sum_{k=1}^{m}e^{-2\pi ik^2/m}\right)
\\&=\sum_{k=1}^{m-1}\sum_{d=1}^{m-k}2\cos\left(\frac{2\pi}{m}(2dk+k^2)\right)+m\end{align}$$
we must prove $\sum_{k=1}^{m-1}\sum_{d=1}^{m-k}2\cos(\frac{2\pi}{m}(2dk+k^2))=0$.If m is small, I can directly calculate, but if m is large, how to do so by induction or any other solutions.
 A: We have
\begin{align*}
|S|^2
&= \sum_{k=0}^{m-1}\sum_{l=0}^{m-1} \exp\left(\frac{2\pi i}{m}(l^2-k^2)\right) \\
&= \sum_{k=0}^{m-1}\sum_{d=0}^{m-1} \exp\left(\frac{2\pi i}{m}(2kd+d^2)\right) \tag{$l\equiv k+d \pmod{m}$} \\
&= \sum_{d=0}^{m-1} \Biggl[ \sum_{k=0}^{m-1} \exp\left(\frac{4\pi i d}{m} k\right) \Biggr] \exp\left(\frac{2\pi i d^2}{m}\right).
\end{align*}
As pointed out by @Cade Reinberger, the geometric sum formula shows that the inner sum only survives with the value $m$ when $d=0$, and hence the desired claim follows.
A: Using the fact that $$\sum_{n=1}^L \cos(a+nd) = \csc\left(\frac d2 \right) \sin\left(\frac{dL}{2} \right) \cos\left(a+\frac d2(L+1)\right), $$ the inner sum can be evaluated exactly to reduce it down to $$- 2\sum_{k=1}^{m-1} \cot\left(\frac{2\pi k}{m} \right ) \sin\left(\frac{2\pi k^2}{m} \right)$$ Then it can be easily shown that $$  \cot\left(\frac{2\pi k}{m} \right ) \sin\left(\frac{2\pi k^2}{m} \right) $$ changes sign under the transformation $k \mapsto m-k$, and hence this sum is equal to the negative of itself, or in other words equals $0$.
