# How to prove this sum related to Legendre symbol

I can see why it is true by writing out some examples, but I'm not sure how one could prove that, with $\left({\cdot\over p}\right)$ as the mod $p$ Legendre symbol

$$\sum_{x=1}^{p-1} \left(\frac{x(x-1)}{p}\right)=-1$$

For example, for $p=5$

$(2/5)+(1/5)+(2/5)=-1$

But could it be shown just from the sum itself?

## 2 Answers

Every $x\in[1,p-1]$ is invertible $\!\!\pmod{p}$ and if we denote with $x^{-1}$ its inverse we have:

$$\sum_{x=1}^{p-1}\left(\frac{x(x-1)}{p}\right) = \sum_{x=1}^{p-1}\left(\frac{x^{-1}}{p}\right)\left(\frac{x-1}{p}\right) = \sum_{x=1}^{p-1}\left(\frac{1-x^{-1}}{p}\right)=\sum_{y=1}^{p-1}\left(\frac{1-y}{p}\right)$$ that is just $$\left(\frac{0}{p}\right)+\sum_{z=2}^{p-1}\left(\frac{z}{p}\right) = -\left(\frac{1}{p}\right)+\sum_{z=1}^{p-1}\left(\frac{z}{p}\right) = -1$$ as wanted.

For $p$ prime $\chi(n) = (\frac{n}{p})$ is a non-principal Dirichlet character $\bmod p$.

Since for $gcd(k,p ) = 1$ : $$\sum_{n=1}^p \chi(n) e^{-2i \pi nk/p} = \overline{\chi(k)} \sum_{n=1}^p \chi(nk) e^{-2i \pi nk/p}=\overline{\chi(k)}\sum_{n=1}^p \chi(n) e^{-2i \pi n/p}$$ we have that its discrete Fourier transform is $\hat{\chi}(k) =\frac{1}{\sqrt{p}}\sum_{n=1}^p \chi(n) e^{-2i \pi nk/p}= \overline{\chi(k)}G(\chi)$ where $G(\chi) = \hat{\chi}(1)$ and $|G(\chi)| = 1$.

Using that the DFT of $\chi(n-1)$ is $\hat{\chi}(k) e^{-2i \pi k/p}$ and the unitary-ness of the DFT : $$\sum_{n=1}^p \chi(n) \overline{\chi(n-1)} = \sum_{k=1}^p \hat{\chi}(k)\overline{\hat{\chi}(k)} e^{2i \pi k/p} = |G(\chi)|^2 \sum_{k=1}^p |\chi(k)|^2 e^{2i \pi k/p}=\sum_{k=1}^{p-1} e^{2i \pi k/p}= -1$$

• I don't understand what happens when $\chi(n)$ is the trivial character. Can you find the mistake ? – reuns Feb 13 '17 at 0:23