Counting solutions to $x^2+y^2 \equiv d \pmod{p}$ for a prime $p \equiv 3 \pmod 4$

Question

For any given $p \equiv 3 \pmod{4}$ and $d=1, 2, \dots, p-1$, we would like to show that there are always exactly $p+1$ solutions to $x^2 + y^2 \equiv d \pmod{p}$. This conjecture comes from some numerical experiments, and certainly holds for all small primes $p \equiv 3 \pmod{4}$.

We can show this in the special case when $d$ is a quadratic residue $\pmod{p}$, but are stuck on the general case.

Answer 1

alright, there are $p^2$ ordered pairs. The only pair giving $x^2 + y^2 = 0$ is $(0,0)$ because $-1$ is not a square.

For each of $(p-1)/2$ residues, there are $p+1$ pairs, total is $ \frac{p^2 - 1}{2}$

Thus $0$ and residues total to $ \frac{p^2 + 1}{2}$

Finally, nonresidues total to $ \frac{p^2 - 1}{2},$ and there are $(p-1)/2$ non-residues. The count for each non-residue is also $p+1$

P.S. the reason the counts are all the same for nonresidues: let $n_1, n_2$ be nonresidues, so there is some nonzero $a$ with $n_2 = n_1 a^2.$ Then we have a bijection of $(x,y)$ pairs: $x^2 + y^2 = n_1 $ maps to $(ax)^2 + ( ay)^2 = n_1 a^2 = n_2$

Answer 2

Well one (maybe overpowered) solution is the following. Consider the curve $$ C: x^2 + y^2 - d = 0$$ in $\mathbb{A}^2_{\mathbb{F}_p}$. Immediately one can note that the projective closure of this curve has "genus $0$" (unless $d = 0$ where it is the union of two lines), so we would expect it to either have $0$ solutions, or $p + 1 = \# \mathbb{P}^1_{\mathbb{F}_p}$ solutions.

One way to see this is to take a point (assuming one exists), then draw lines with rational slope through it - you'll see each intersects at a unique second point, so you get $p$ more points, one for each choice of slope.

In particular $\# C(\mathbb{F}_p)$ should be $0, p$ or $p + 1$. The second and third cases differ depending on if there is a point at infinity.

There are $(p+1)/2$ squares in $\mathbb{F}_p$ so $(p+1)/2$ choices for both $x^2$ and $-y^2 + d$, so $C(\mathbb{F}_p)$ cannot be empty. In particular $\# C(\mathbb{F}_p)$ is either $p$ or $p + 1$.

Setting $x = X/Z$ and $y = Y/Z$ we have the equation $X^2 + Y^2 - dZ^2 = 0$ for the projective closure. When $Z = 0$ (i.e., the line at infinity) we have $X^2 + Y^2 = 0$. Thus there is a point at infinity if and only if $-1$ is a quadratic residue modulo $p$. This is the case if and only if $p \equiv 1 \pmod{4}$.

Therefore we have the following cases. When $d = 0$ there are $p^2$ solutions, when $d \neq 0$ there are $p$ solutions if $p \equiv 1 \pmod{4}$ and $p + 1$ solutions if $p \equiv 3 \pmod{4}$.