Show that $p\equiv 3\pmod 4$ being prime implies $x^2+y^2\equiv n\pmod p$ has $p+1$ solutions

Question

Let $p$ be an odd prime with $p\equiv 3\pmod 4$. Show that for $n\ne 0$, $x^2+y^2\equiv n\pmod p$ has $p+1$ solutions.

I tried using some laws of quadratic reciprocity but got absolutely nowhere:(

Answer 1

Define the following two sets: $$A_\pm := \left\{(x, y)\in\mathbb F_p^2\left| \left(\frac{x^2+y^2}{p}\right) = \pm 1\right.\right\}$$

Since $p\equiv 3\mod 4$, there is only one solution to $x^2+y^2=0$ in $\mathbb F_p$, namely $(0, 0)$. Therefore: $$\mathbb F_p^2 = A_+\dot\cup A_-\dot\cup\{(0, 0)\}$$

Thus, $|A_+|+|A_-| = p^2-1$. Let $n_0:=\min\left\{n\in\{1,\ldots,p-1\}\left|\left(\frac np\right)=-1\right.\right\}$. Then, there is $m\in\mathbb F_p$ with $m^2 = n_0-1+p\mathbb Z$ and $(m, 1)\in A_-$. Regard the following map: $$A_+\to A_-, (x, y)\mapsto (mx-y, x+my)$$

This map (multiplication by $m+\sqrt{-1}$ in $\mathbb F_p[\sqrt{-1}]$) is bijective since the following is an inverse: $$A_-\to A_+, (x, y)\mapsto \left(\frac{y+mx}{n}, \frac{my-x}{n}\right)$$

Therefore: $$|A_+| = |A_-| = \frac{p^2-1}{2} = (p+1)\frac{p-1}{2}$$

Let $a, b\in\mathbb F_p$ such that $\left(\frac ap\right) = \left(\frac bp\right)\neq 0$. Then, there is $c\in\mathbb F_p$ such that $b = ac^2$. The following map is bijective: $$\{(x, y)\in\mathbb F_p^2|x^2+y^2 = a\}\to \{(x, y)\in\mathbb F_p^2|x^2+y^2 = b\}, (x, y)\mapsto (cx, cy)$$

In particular, these two sets have the same cardinality. Since $\mathbb F_p$ has $\frac{p-1}{2}$ quadratic residues and non-residues each, it follows that for any $a\in\mathbb F_p\setminus\{0\}$: $$|\{(x, y)\in\mathbb F_p^2|x^2+y^2 = a\}| = \frac{\left|A_{\left(\frac ap\right)}\right|}{(p-1)/2} = p+1$$

Answer 2

First note that the the norm function $N: \mathbb{Z}_p\times \mathbb{Z}_p \to \mathbb{Z}_p$ defined as $(x, y) \to x^2+y^2$ mod $p$ is `multiplicative', when the multiplication of two tuples $(x_1,y_1)$ and $(x_2,y_2)$ is defined as $(x_1,y_1)\cdot (x_2,y_2) = (x_1x_2-y_1y_2, x_1y_2+y_1x_2)$. Notice that this is basically complex multiplication.

It is clear that the set of tuples with non-zero norm form a group, with a subgroup given by those tuples with unit norm. The $p-1$ different cosets of this subgroup are exactly the set of tuples with fixed norm. Thus, by Lagrange the number of solutions is independent of $n$ if $n$ is non-zero.

Finally, note that -1 is not a square in $\mathbb{Z}_p$ if $p = 3$ mod 4. This means that the only solution to $x^2+y^2 = 0$ in $\mathbb{Z}_p$ is $x=0, y=0$. Since there are $p^2$ tuples, we have that the number of solutions for $n\neq 0$ is $\frac{p^2-1}{p-1} = p+1$.

There's probably a faster way of seeing this, but this is how I think about it. This generalises also nicely to other settings, for example when $p=1$ mod 4, or when the equation is given by a different norm function.