# Prove that if p is an odd prime, the number of residues x modulo p for which both x and x+1 are quadratic residucs

Prove that if p is an odd prime, then the number of residues x modulo p for which both x and x+1 are quadratic residucs is $\frac{p-(-1)^\frac{p-1}{2}}{4}-1$

I know that 0 is neither a quadratic residue nor a quadratic non-residue, so there is a "-1", but I have no idea how $\frac{p-(-1)^\frac{p-1}{2}}{4}$ comes. Can anyone help me with it? Thank you very much!

• What have you tried? Where did you get stuck? Knowing what you know makes it much easier to help you – Stella Biderman Oct 29 '17 at 3:31

Let $N(a,b)$ denote the number of integers $x$ among $1,2,\ldots,p-2$ such that $(x|p)=a$ and $(x+1|p)=b$. Let $0<x<p-1$. Note that if $a=(x|p)$ then $1+a\cdot (x|p)=2$ and if $a\neq (x|p)$ then $1+a\cdot (x|p)=0$. This says $$\Bigl[1+a\cdot (x|p)\Bigr] \cdot \Bigl[1+b\cdot(x+1|p)\Bigr]=\begin{cases} 4 & \mbox{if a=(x|p) and b=(x+1|p)} \\ 0 & \mbox{otherwise}.\end{cases}$$ This says $$4 \cdot N(a,b)=\sum_{x=1}^{p-2}\Bigl[1+a(x|p)\Bigr] \cdot \Bigl[1+b(x+1|p)\Bigr]$$ Expanding and evaluating you get $$4\cdot N(a,b)=p-2-a(-1|p)-b+ab\sum_{x=1}^{p-2}(x^2+x|p)$$
Put $a=b=1$, because you want $x$ and $x+1$ both to be quadratic residues. Then we get $$N(1,1)= \frac{1}{4}\cdot \left[p-2-(-1)^{p-1/2}-1+\sum_{x=1}^{p-2}(x^{2}+x|p)\right]$$ Now note that $\sum_{x=1}^{p-2}(x^{2}+x|p)=-1$, Therefore $$N(1,1)=\frac{p-4-(1)^{p-1/2}}{4}$$
• Why $\sum_{x=0}^{p-1} (\frac{x^2+x}{p}) =0$ ? – reuns Oct 29 '17 at 6:52