Counting pairs $(n,n+1)$ where $n$ and $n+1$ are both quadratic residues, etc.?

Question

This is an interesting problem I read that has me stumped.

Let $(RR)$ denote the number of pairs $(n,n+1)$ in the set $\{1,2,\dots,p-1\}$ such that $n$ and $n+1$ are both residues modulo $p$. Let $(NR)$ denote the pairs where $n$ is a nonresidue, and $n+1$ is a residue modulo $p$. Do the same for $(NN)$ and $(RN)$.

The question is, what are $(RR)+(RN),(NR)+(NN),(RR)+(NR),(RN)+(NN)$?

I know that if $g$ is a primitive root, then the residues are the even powers of $g$, and the nonresidues are the odd powers of $g$. So the pairs in $(RR)$ have form $(g^{2k},g^{2j})$, and I would like to count the pairs that can be expressed as $n=g^{2k},n+1=g^{2j}$. This implies $g^{2j}-g^{2k}=1=g^{p-1}$. I could set up similar equations for the other three types of pairs, but I don't see any thing nice to grab onto and work with. Maybe computing $(RR)+(RN)$ is easier than computing $(RR)$ and $(RN)$ separately for some reason?

How could one approach computing these? Thank you.

Source: Ireland/Rosen #5.29

Answer 1

Let $p$ be odd. We look at $(RR)+(RN)$. This is almost the number of QR. The only way a QR can fail to be followed by a QR or an NR is if the QR is at $p-1$. This is the case iff $p\equiv 1\pmod{4}$.

So when $p\equiv 1\pmod{4}$, we have $(RR)+(RN)=\frac{p-1}{2}-1$. When $p\equiv -1\pmod{4}$, we have $(RR)+(RN)=\frac{p-1}{2}$. I have not done the other questions. They look much the same. For the last two we have to travel backwards, and note that $1$ is always a QR.

Answer 2

To compute separately see Apostol Chapter 9 Ex 5, p201.

With $\alpha$,$\beta$ being $\pm1$ let $N(\alpha,\beta)$ denote the number of integers $x$ among $1,2,\dots,p-2$ such that $(x|p)=\alpha$ and $(x+1|p)=\beta$ where $p$ is an odd prime. So $N(1,-1)=(RN)$ above. Then

$4N(\alpha,\beta)=\displaystyle\sum_{x=1}^{p-2}(1+\alpha(x|p))(1+\beta(x+1|p))$

since $1+\alpha(x|p)=2$ if $(x|p)=\alpha$; and is $0$ otherwsie. Similarily for $\beta$ so that $(1+\alpha(x|p))(1+\beta(x+1|p))=4$ if $(x|p)=\alpha$ and $(x+1|p)=\beta$; and is $0$ otherwise.

Then expanding the sum we get

$4N(\alpha,\beta)=p-2-\beta-\alpha\beta-\alpha(-1|p)$

using

$\displaystyle\sum_{x=1}^{p-2}(x|p)=-(-1|p)$; $\displaystyle\sum_{x=1}^{p-2}(x+1|p)=-1$ and $\displaystyle\sum_{x=1}^{p-2}(x(x+1)|p)=-1$.