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

up vote 6 down vote accepted

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.

  • There's something not displaying properly in my computer's rendition of the formula for the number of solutions. Thanks for the answer. My purely experimental version of the formula is Ceiling[p/8] with no exceptions as far as I carried the computation. – David S. Newman Jun 11 '14 at 21:47
  • You could also say floor((p+7)/8) for all odd primes, and floor (p/8) for all even primes. – The Masked Avenger Jun 11 '14 at 22:31
  • @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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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