Do not attempt to list

• For odd prime $p$ , in cyclic interval $[0, p-1]$ , we have $\frac{p+1}{4}$ consecutive $q.r$ if $p \equiv -1 \pmod{4}$

• So for $p = 2011$ , we have $503$ cyclically consecutive $q.r$ But $n$ and $n + 1$ to be counted here only if $n$ is positive integer $\leq 2003$

• We can manually find $2^{1005} \equiv -1 \pmod{2011}$ and $3^{1005} \equiv -1 \pmod{2011}$ So $2$ and $3$ are $q.n.r$ . So $6$ must be $q.r$ . Also $1$ and $4$ are always $q.r$

• So $-2$ , $-3$ will be $q.r$ and $-1, -4, -6$ will be $q.n.r$ mod 2011 (as $2011 \equiv -1 \pmod{4}$ ) means $2008, 2009$ are $q.r$ and $2005, 2007, 2010$ are $q.n.r$ (no conclusion needed about $2006$ )

• So only $n=0, n=2008$ need to be rejected out of $503$ consecutive $q.r$

• So answer $503 - 2 = \boxed{501}$

The main result we will prove is:

• if $p \equiv 3 \pmod 4$ is prime, then there are exactly $\frac {p-3} 4$ pairs $(x, y)$ of quadratic residues modulo $p$ , $x, y \not\equiv 0 \pmod p$ , such that $y - x \equiv 1 \pmod p$ .

E.g. when $p=19$ , the quadratic residues are 0, 1, 4, 5, 6, 7, 9, 11, 16, 17, so the four pairs are (4, 5), (5, 6), (6, 7), (16, 17).

$-$

First, suppose we have $a^2 - b^2 \equiv 1 \pmod p$ . This gives $(a-b)(a+b) \equiv 1 \pmod p$ , so there are exactly $p-1$ pairs of $(a, b)$ satisfying this congruence, which are in bijective correspondence with the pairs of $(x,y)$ modulo $p$ satisfying $xy \equiv 1\pmod p$ , via:

$(x,y)\mapsto (a,b) \equiv \left(\frac{x+y} 2, \frac{y-x}2\right) \mod p.$

The unwanted case $b^2 \equiv 0 \pmod p$ holds if and only if $x\equiv y\pmod p$ , i.e. if and only if $(x,y) \equiv (1,1), (-1,-1) \pmod p$ .

The unwanted case $a^2 \equiv 0\pmod p$ does not occur since $p\equiv 3 \pmod 4$ so -1 is not a quadratic residue.

Now we are left with $p-3$ ordered pairs of $(x,y)$ .

Finally, suppose the pairs $(x,y)$ and $(x',y')$ give rise to $(a^2, b^2)$ and $(a'^2, b'^2)$ respectively. Then the two latter pairs are equal if and only if:

$\begin{aligned}a'^2 \equiv a^2 &\pmod p \iff a' \equiv \pm a\pmod p,\\ b'^2 \equiv b^2 &\pmod p\iff b' \equiv \pm b\pmod p\end{aligned}$

thus giving rise to four possible cases:

$a'\equiv a, b'\equiv b\pmod p \iff x'\equiv x, y'\equiv y\pmod p;$ $a'\equiv -a, b'\equiv b\pmod p\iff x'\equiv -y, y'\equiv -x\pmod p;$ $a'\equiv a, b'\equiv -b\pmod p\iff x'\equiv y, y'\equiv x\pmod p;$ $a'\equiv -a, b'\equiv -b\pmod p\iff x'\equiv -x, y'\equiv -y\pmod p.$

It is easy to see that for the $p-3$ pairs of $(x,y)$ , $x \not\equiv \pm y\pmod p$ so these four cases are all distinct. Hence there are exactly $\frac{p-3} 4$ pairs of $n, n+1$ which are both quadratic residues, where $1\le n\le p-2$ .

$-$

For our problem, $p=2011$ so there are $\frac {2011 - 3} 4 =502$ such pairs. It remains to subtract from this the number of pairs $(n, n+1)$ , for which $2005 \le n \le 2009$ . The only such pair is (2006, 2007), so the answer is $\fbox{501}$ .