<s>[INST] 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.
 [/INST] 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$
</s>