# Sum of Legendre symbol $\left(\frac{n^2-a}{p}\right)$ (More explanation)

In fact, there are several same questions, but I still post it here:

If $$(a,p)=1$$, $$p$$ an odd prime, then $$\sum_{n=1}^{p}\left(\frac{n^2+a}{p}\right)=-1$$.

In those same posts, I tried to read the proof https://artofproblemsolving.com/community/c146h150500p849406 and Number Theory: Solutions of $$ax^2+by^2\equiv1 \pmod p$$. But I cannot understand the full proof. Instead, I was stuck in some way. Right now, I am trying to use "Eulers' Criterion" to do this question: $$\left(\frac{n^2+a}{p}\right)\equiv (n^2+a)^{\frac{p-1}{2}}$$ (mod $$p$$), thus: $$\sum_{n=1}^{p}\left(\frac{n^2+a}{p}\right)\equiv \sum_{n=1}^{p}(n^2+a)^{\frac{p-1}{2}}$$ (mod $$p$$).

Then, I tried to apply the binomial expansion to further simplify. And that is the step where I was stuck. Can anyone further explain the mechanism?

• Do you know the formula for $1^k + 2^k + \cdots + p^k$ modulo $p$ when $k$ is an integer between $0$ and $p-1$ ? That said, you will need some care in your approach: If you prove that the sum is $\equiv -1 \mod p$, it won't directly follow that it is $= -1$ as an integer (it could be $p-1$, too). – darij grinberg Nov 15 '18 at 15:18
• Also, it is worth specifying where exactly you're stuck, e.g. in comments under the respective answers. – darij grinberg Nov 15 '18 at 15:20
• No. But i am searching and reading after your comment. I saw this in one of the proof. So, this is important in this question? – Jason Ng Nov 15 '18 at 15:20
• Yes, it is. See math.stackexchange.com/questions/433678/… . – darij grinberg Nov 15 '18 at 15:22
• When I expand $(n^2+a)^{p-1/2}$, I know the first term is $n^{p-1}$, which is 1 modulo $p$. But the rest of the terms I don't know how to simplify under modulo $p$. – Jason Ng Nov 15 '18 at 15:22