Sum of Legendre sequence $S=\sum_{x=0}^{p-1}\left(\frac{x(x+k)}{p}\right)$

Question

Calculate the sum of Legendre sequence $S(x):=\displaystyle \sum_{x=0}^{p-1}\left(\dfrac{x(x+k)}{p}\right)$ with $p > 3$ prime number, $k \in \mathbb{N}$ and $\text{gcd}(p,k)=1$.

I have tried to find the solution but I did not succeed. I would appreciate if somebody could help me. Thank you.

Answer 1

Dropping the term corresponding to $x=0$ and making the substitution $x=ky$, we get $$ S(k) = \sum_{y=1}^{p-1} \left(\frac{ky(ky+k)}p\right) = \sum_{y=1}^{p-1} \left(\frac{y(y+1)}p\right),\quad k\ne 0. $$ This shows that the sum is independent of $k$. Consequently, $$ S(k) = \frac1{p-1}\,\sum_{k=1}^{p-1} \sum_{x=1}^{p-1} \left(\frac{x(x+k)}p\right) = \frac1{p-1}\,\sum_{x=1}^{p-1} \left(\frac xp\right)\sum_{k=1}^{p-1}\left(\frac{x+k}p\right). $$ In the inner sum in the RHS, $x+k$ runs over all elements of $\mathbb F_p$ other than $x$. As a result, the sum is equal to $-\left(\frac{x}p\right)$, leading to $$ S(k) = \frac1{p-1}\, \sum_{x=1}^{p-1} \left(\frac xp\right)\cdot\left(-\left(\frac xp\right)\right) = -1, \quad k\in\mathbb F_p^\times. $$

Answer 2

Here's a completely different solution that might be of interest.

First note that $$\sum_{x=0}^{p-1} x^j$$ is $0\bmod p$ for $0\leq j\leq p-2$ (as can be shown by using primitive roots*), and $$\sum_{x=0}^{p-1}x^{p-1}\equiv -1\bmod p,$$ as there are $p-1$ terms that are $1$ and one term ($x=0$) that is $0$. We also have the identity $$\left(\frac{x}{p}\right)\equiv x^{(p-1)/2}\bmod p.$$ Now, $$\sum_{x=0}^{p-1}\left(\frac{x(x+k)}{p}\right)=\sum_{x=0}^{p-1}x^{(p-1)/2}(x+k)^{(p-1)/2}.$$ When this is expanded, every term is of degree $<p-1$ except for the leading term $x^{p-1}$ (with coefficient $1$), so the sum is $-1\bmod p$. As it is a sum over $p-1$ elements of $\{-1,0,1\}$, not all of which are $1$ (this is where we use that $p\nmid k$), so the sum is in fact exactly $-1$.

*To elaborate more on the primitive root idea; if $j<p-1$, let $g$ be a primitive root $\bmod p$. Then

\begin{align} \sum_{x=0}^{p-1}x^j &=\sum_{x=1}^{p-1}x^j\\ &\equiv\sum_{t=0}^{p-2}(g^t)^j\\ &=\sum_{t=0}^{p-2}(g^j)^t\\ &=\frac{g^{j(p-1)}-1}{g^j-1}=0. \end{align}