Counting the number of solutions of equation $x^2 + y^2 = 1$ over $\Bbb Z/p$ List proofs of the fact that the number of solutions to $x^2 + y^2 = 1$ over $\Bbb Z/p$, where $p$ is a prime $\neq 2$, is $p-(-1)^{\frac{p-1}2}$. I thought of two.
I write one below.

Either $p = 2$ or $p \equiv 1 \pmod{4}$ or $p \equiv 3 \pmod{4}$.
If $p = 2$ then $f(x) = x^2$ is a bijection so there is always a unique $y = f^{-1}(1 - x^2)$. Therefore the number of solutions is $p$.
If $p \equiv 1 \pmod{4}$ then $(-1 \mid p) = (-1)^{\frac {p-1} 2} = 1$, so there is an $i \in \Bbb Z/p$ for which $i^2 = -1$. $x^2 + y^2 = 1 \iff (x+iy)(x-iy) = 1$. First, count the number of $(u,v) \in (\Bbb Z/p)^2$ for which $uv = 1$; clearly that's $p - 1$. For each $(u,v)$ we can set up a system of linear equations $$\left(\begin{array}\\1 & i \\ 1 & -i\end{array}\right)\left(\begin{array}\\x \\ y\end{array}\right) = \left(\begin{array}\\u \\ v\end{array}\right)$$ which has a unique solution for $(x,y)$ because $\det = -2i$. Therefore the number of solutions is $p - 1$.
If $p \equiv 3 \pmod{4}$ then $(-1 \mid p) = (-1)^{\frac{p-1}2} = -1$, so $-1$ is not a residue. Note that for any $x \not\in \{-1,+1\}$, $(\exists y: x^2 + y^2 = 1) \iff \not\exists y: x^2 - y^2 = 1$. This is because $(1 - x^2 \mid p) = (-1 \mid p)(x^2 - 1 \mid p) = -(x^2 - 1 \mid p)$. For this reason, the three sets $A = \{x \mid \exists y: x^2 + y^2 = 1, x^2 \neq 1\}$, $B = \{x \mid \exists y: x^2 - y^2 = 1, x^2 \neq 1\}$ and $C = \{-1,+1\}$ form a partition of $\Bbb Z/p$. This implies that $|A| + |B| + |C|= |\Bbb Z /p|$. $|\Bbb Z/p| = p$. We shall now count the elements of $B$. To do this, determine $|\{(x,y) \mid x^2 - y^2 = 1\}|$, which by a method used above is $p - 1$. Any given $x \in B$ corresponds to two $y$-values on $x^2 - y^2 = 1$ so $|B| = \dfrac{p-1 - 2}{2} = \dfrac{p-3}2$. Now we know $|A| = p - 2 - \dfrac{p-3}{2} = \dfrac{p-1}2$. Every $x \in A$ corresponds to two $y$-values for which $x^2 + y^2 = 1$. So $|\{(x,y) \mid x^2 + y^2 = 1\}| = 2|A| + 2 = p+1$.
