# How does this sequence grow

Let $a(n)$ be the number of solutions of the equation $a^2+b^2\equiv -1 \pmod {p_n}$, where $p_n$ is the n-th prime and $0\le a \le b \le \frac{p_n-1}2$. Is the sequence $a(1),a(2),a(3),\dots$ non-decreasing? Data for the first thousand values of the sequence supports this conjecture.

Here is an example for $n=5$:
The fifth prime is 11. The equation $a^2+b^2 \equiv -1 \pmod {11}$ has just two solutions with the required conditions on $a$ and $b$, namely: $1^2+3^2=10$ and $4^2+4^2=32$.

Here are the first fifty values of $a(n)$: 0,1,1,1,2,2,3,3,3,4,4,5,6,6,6,7,8,8,9,9,10,10,11,12,13,13,13,14,14,15,16,17,18,18,19,19,20,21,21,22,23,23,24,25,25,25,27,28,29,29

-

The answer is yes, and the number of solutions with a prime $p$ is $\lfloor \frac{p+5}{8} \rfloor$ when $p \not\equiv 1 \pmod{8}$ and is $\lfloor \frac{p+5}{8} \rfloor + 1$ when $p \equiv 1 \pmod{8}$.
The equation $a^{2} + b^{2} + c^{2} = 0$ defines a conic in $\mathbb{P}^{2}/\mathbb{F}_{p}$. If $p > 2$ this conic has a point on it (by the standard pigeonhole argument that there is a solution to $a^{2} + b^{2} \equiv -1 \pmod{p}$), and so it is isomorphic to $\mathbb{P}^{1}$. Hence, there are $p+1$ points on this conic in $\mathbb{P}^{2}$. Every such point has the form $(a : b : 0)$ or $(a : b : 1)$. If $p \equiv 3 \pmod{4}$, there are no points of the form $(a : b : 0)$, while if $p \equiv 1 \pmod{4}$, then there is a solution to $x^{2} \equiv -1 \pmod{p}$ and $(1 : \pm x : 0)$ give two such points.
Hence the number of solutions to $a^{2} + b^{2} \equiv -1 \pmod{p}$ with $0 \leq a \leq p-1$, $0 \leq b \leq p-1$ is $p+1$ or $p-1$ depending on what $p$ is mod $4$. Now it takes a bit more thought and some careful keeping track of solutions with $a$ or $b$ equal to zero, or $a = b$ to derive the formula.
@David - Your formula and mine are the same if $p > 2$. Note that Ceiling[2/8] = 1. –  Jeremy Rouse Jun 12 '14 at 10:36