Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Hint: can you spot some mutually exclusive combinations which might combine neatly ... – Mark Bennet Jan 7 '13 at 23:22
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks again, I'll try my best to work out the rest. – Noomi Holloway Jan 8 '13 at 8:00

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


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



$\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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.