# Prove that $\sum_{X=0}^{p-1} \left(\frac{X^{2}+A}{p}\right)=-1$

Let $$\left(\dfrac{a}{p}\right)$$ denote the Legendre symbol and $$p \geq 3$$ a prime number and $$A$$ an integer such that $$p \nmid A$$. Prove that $$\sum_{X=0}^{p-1} \left(\dfrac{X^{2}+A}{p}\right)=-1 .$$

I wasn't sure how to manipulate this sum. Maybe if we show that $$\left(\dfrac{X^{2}+A}{p}\right)$$ can't be a quadratic residue for more than some amount of values it will help.

Fix an odd prime natural number $$p$$. Let $$S_p(A):=\sum_{x\in\mathbb{F}_p}\,\left(\frac{x^2+A}{p}\right)$$ for all $$A\in\mathbb{F}_p^\times$$, where $$\mathbb{F}_p^\times$$ is the group $$\mathbb{F}_p\setminus\{0\}$$ of units modulo $$p$$. Note that \begin{align} S_p(A) &=\left(\frac{A}{p}\right)+\sum_{x\in\mathbb{F}_p^\times}\,\left(\frac{x^2+A}{p}\right)=\left(\frac{A}{p}\right)+\sum_{x\in\mathbb{F}_p^{\times}}\,\left(\frac{1+Ax^2}{p}\right)\left(\frac{x^{-2}}{p}\right) \\ &=\left(\frac{A}{p}\right)+\sum_{x\in\mathbb{F}_p^{\times}}\,\left(\frac{1+Ax^2}{p}\right)=\left(\frac{A}{p}\right)\,\left(1+\sum_{x\in\mathbb{F}_p^{\times}}\,\left(\frac{x^2+A^{-1}}{p}\right)\right) \\ &=\left(\frac{A}{p}\right)\left(1-\left(\frac{A^{-1}}{p}\right)+\sum_{x\in\mathbb{F}_p}\,\left(\frac{x^2+A^{-1}}{p}\right)\right)=\left(\frac{A}{p}\right)-1+\left(\frac{A}{p}\right)\,S_p\left(A^{-1}\right)\,. \end{align} If $$\left(\dfrac{A}{p}\right)=-1$$, then we have $$S_p(A)+S_p\left(A^{-1}\right)=-2\,.\tag{1}$$

From the claim in this answer, we have $$-1=-\left(\frac{1}{p}\right)=\sum_{y\in\mathbb{F}_p}\,\left(\frac{y(y+A)}{p}\right)=\frac{1}{2}\,\sum_{x\in\mathbb{F}_p^{\times}}\,\left(\frac{x^2+A}{p}\right)+\frac{1}{2}\,\sum_{x\in\mathbb{F}_p^{\times}}\,\left(\frac{x^2+Au}{p}\right)\,,$$ where $$u$$ is an arbitrary quadratic nonresidue modulo $$p$$. Hence, $$S_p(A)+S_p(Au)=-2\,.\tag{2}$$

If $$\left(\dfrac{A}{p}\right)=-1$$, then $$(2)$$ with $$u:=A^{-1}$$ yields $$S_p(A)+S_p(1)=-2\,.\tag{3}$$ Comparing $$(3)$$ with $$(1)$$, we have $$S_p\left(A^{-1}\right)=S_p(1)$$. However, this is true for all $$A$$ with $$\left(\dfrac{A}{p}\right)=-1$$, whence $$S_p(A)=S_p(1)$$. Consequently, $$S_p(A)=-1$$.

Now, if $$\left(\dfrac{A}{p}\right)=+1$$, then we know from the paragraph above that $$S_p(Au)=-1$$. Ergo, $$S_p(A)=-1$$ as well.

In general, let $$p$$ be an odd prime natural number and $$a,b,c\in\mathbb{F}_p$$. We have $$\sum_{x\in\mathbb{F}_p}\,\left(\dfrac{ax^2+bx+c}{p}\right)=\begin{cases} p\,\left(\dfrac{c}{p}\right)&\mbox{if }a=0\mbox{ and }b=0\,,\\ 0&\mbox{if }a=0\mbox{ and }b\neq0\,,\\ (p-1)\,\left(\dfrac{a}{p}\right)&\mbox{if }a\neq 0\mbox{ and }b^2-4ac=0\,,\\ -\left(\dfrac{a}{p}\right)&\mbox{if }a\neq 0\mbox{ and }b^2-4ac\neq 0\,.\\ \end{cases}$$

• Another approach to the "In general" identity: Let $L = \sum\limits_{x \in \mathbb{F}_p} \left(\dfrac{ax^2+bx+c}{p}\right)$. Then, $L \in \left\{-p,-p+1,\ldots,p\right\}$. But recall that $\left(\dfrac{u}{p}\right) \equiv u^{\left(p-1\right)/2} \mod p$ for all integers $u$. Thus, $L \equiv \sum\limits_{x \in \mathbb{F}_p} \left(ax^2+bx+c\right)^{\left(p-1\right)/2} \mod p$. But $\left(ax^2+bx+c\right)^{\left(p-1\right)/2}$ is a polynomial of degree $\leq p-1$ in $x$, and its $x^{p-1}$-coefficient is $a^{\left(p-1\right)/2}$. Hence, ... Aug 8, 2019 at 8:19
• ... we know that $L$ is congruent (mod $p$) to the sum of all values of this polynomial over $\mathbb{F}_p$. However, it is known that such a sum is always congruent to minus the $x^{p-1}$-coefficient (since $\sum_{x \in \mathbb{F}_p} x^i = 0$ for all $i < p-1$ and since $\sum_{x \in \mathbb{F}_p} x^{p-1} = -1$). Thus, $L \equiv - a^{\left(p-1\right)/2} \equiv - \left(\dfrac{a}{p}\right) \mod p$. Combining this with $L \in \left\{-p,-p+1,\ldots,p\right\}$, we have thus narrowed down the value of $L$ to two or three options. But we also know the parity of $L$: If $b^2 - 4ac \neq 0$, then ... Aug 8, 2019 at 8:22
• ... (assuming $a \neq 0$) either none or two of the addends of the sum $L = \sum\limits_{x \in \mathbb{F}_p} \left(\dfrac{ax^2+bx+c}{p}\right)$ are zero (because the discriminant of a quadratic polynomial tells us whether it has exactly one root), and thus $L$ is odd (since all remaining addends in this sum are odd); otherwise, exactly one of these addends is zero, and thus $L$ is even. In either case, this uniquely determines the value of $L$ when $a \neq 0$. The case $a = 0$ is easy and can be handled separately. Aug 8, 2019 at 8:30