2
$\begingroup$

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Jun 11, 2014 at 21:47
  • $\begingroup$ You could also say floor((p+7)/8) for all odd primes, and floor (p/8) for all even primes. $\endgroup$ Jun 11, 2014 at 22:31
  • $\begingroup$ @David - Your formula and mine are the same if $p > 2$. Note that Ceiling[2/8] = 1. $\endgroup$ Jun 12, 2014 at 10:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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