Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

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.

share|improve this answer
    
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 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 at 22:31
    
@David - Your formula and mine are the same if $p > 2$. Note that Ceiling[2/8] = 1. –  Jeremy Rouse Jun 12 at 10:36

Your Answer

 
discard

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.