<s>[INST] Alternative way to count the number of solutions to the equation $x^2 + y^2 = -1$ over $\Bbb Z /p$ 
$x^2 + y^2 = -1$ is a weird equation because it has no solutions over $\Bbb R$. I want to count the number of solutions it has over $\Bbb Z / p$ where $p$ is prime.

If $p = 2$ then it has $p$ solutions. This is to do with the fact that squaring is a field automorphism.
If $p \equiv 1 \pmod{4}$ then there is an $i$ such that $i^2 = -1$ so $$x^2 + y^2 = -1 \implies \left({x \over i}\right)^2 + \left({y \over i}\right)^2 = 1 \implies \left({x \over i} + y \right)\left({x \over i} - y \right) = 1$$ which has $p - 1$ solutions.
If $p \equiv 3 \pmod{4}$ then the situation is more complicated. The thing I noticed is that $A = \{x \mid x^2 + y^2 = -1\}$ and $B = \{x \mid y^2 - x^2 = 1\}$ form a partition of $\Bbb Z/p$. Reason being that $x \not\in A \implies (-1 - x^2 \mid p) = -1 \implies (1 + x^2 \mid p) = 1 \implies (\exists y)\,1+x^2 = y^2 \implies x \in B$, and vice versa. Also notice that $A \cap B = \emptyset$. So we get $|A| = |\Bbb Z / p| - |B| = p - |B|$. To determine $|B|$, use the fact that for every $(x,y)$ for which $y^2 - x^2 = 1$, $(x,-y)$ also satisfies the equation, so $|B|$ is the number of solutions to $y^2 - x^2 = 1$ divided by $2$, which is $\frac{p-1}{2} \therefore \,|A| = {p + 1 \over 2}$. Now it's easy to see that the number of solutions to $x^2 + y^2 = -1$ is $2|A|$ which is $p+1$.
Any quicker method?
 [/INST] Given a finite field $F$, let $C = F[i]/(i^2+1)$. Define the mapping $N:C \to F$ by $N(x+iy) = x^2 + y^2$ and note that it's a multiplicative homomorphism from $C^*$ to $F^*$.
Now let $X = \{x \in C \mid N(x) = 1\}$ and $Y = \{x \in C \mid N(x) = -1\}$. The aim is to determine $|Y|$.
Note that there exists an $e \in Y$. I will omit the proof.
Define the mapping $f: X \to Y$ by $f(x) = ey$. First, the codomain is correct because given $x \in X$, $N(ex) = N(e)N(x) = (-1) \times 1 = -1$. Second, the mapping is injective because $f(x) = f(x') \implies ex = ex' \implies x = x'$. Finally, the mapping is surjective because given $y \in Y$, $N\left({y \over e}\right) = 1$ so ${y \over e} \in X$ and $f\left(y \over e\right) = e{y \over e} = y$.
So $f$ is a bijection. This implies that we only need to count $X$ to find $|Y|$. Here are some ways to do that.
</s>