I want to find the number of unordered pairs $\{x,y\}\in \mathbb{F}_p$ such that $x^2+y^2=1$.
I've found this answer (#3) that solves this for the more general case of $ax^2+by^2=c$ mod $p$. Something worth noting is that my problem is symmetric in $x$ and $y$, so some solutions are counted twice and others only once, but unfortunately, I can't seem to be able to apply that to correctly count all solutions, it doesn't match what I get for small $p$s. Could you please help me understand how to apply that method to my problem? Also, if you find a more fundamental and simple way to solve this, please share (without projective geometry, I'm not familiar with it). Thanks.
Define $R=\mathbb{F}_p^2$. Define the product on $R$ by $(a,b) \cdot (c,d)=(ac-bd, ad+bc)$ and notice that it is commutative and associative.
You can have a better idea of $R$ by imagining that formally $(a,b)=a+ib$ with $i^2=-1$.
Let $f: R \rightarrow \mathbb{F}_p$ be defined by $f(a,b)=a^2+b^2$.
Note that $f$ is multiplicative and surjective.
Let $G$ be the set $f^{-1}(\mathbb{F}_p^*)$. Then $\mu: G \rightarrow \mathbb{F}_p^*$ is a surjective group morphism. We actually want to determine the cardinality of the kernel of $\mu$, which is $k=\frac{|G|}{p-1}=\frac{p^2}{p-1}-\frac{|f^{-1}\{0\}|}{p-1}$.
So it just remains to study the fiber $f^{-1}\{0\}$.
If $p+1$ is divisible by $4$, then $-1$ isn’t a square mod $p$, from which it follows that $f(a,b)=0$ iff $a=b=0$. Therefore $k=\frac{p^2-1}{p-1}=p+1$.
If $p-1$ is divisible by $4$, then there is a square root of $-1$ (which we denote as $j$), and $a^2+b^2=0$ iff $(a+jb)(a-jb)=0$.
Now, it is easy to check that $g: \mathbb{F}_p^2 \rightarrow \mathbb{F}_p^2$ given by $g(a,b)=(a-jb,a+jb)$ is a bijection. Therefore, the cardinality of $f^{-1}\{0\}$ is that of $\{(a,b),\, ab=0\}$, which is thus $2p-1$. Hence, $k=\frac{p^2-(2p-1)}{p-1}=p-1$.
To summarize: the cardinality is $p+1$ if $p=3$ mod $4$, $p-1$ if $p=1$ mod $4$, $2$ if $p=2$.