Counting solutions to $x^2+y^2 \equiv d \pmod{p}$ for a prime $p \equiv 3 \pmod 4$ 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.
 A: 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$
A: 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}$.
