Counting the solutions of $x^2 \equiv y^2-d \pmod p$

Solution 1:

We are looking at the congruence $(x-y)(x+y)\equiv d\pmod{p}$. If $d$ is divisible by $p$, the solutions are $(a,a)$ and $(a,-a)$, where $a$ travels from $0$ to $p-1$. Since $p$ is odd, these are all distinct modulo $p$, except when $a=0$. So there are $2(p-1)+1=2p-1$ solutions.

Suppose now that $d$ is not divisible by $p$. Let $x-y = a$, where $a$ travels from $1$ to $p-1$ (clearly $y-x$ cannot be congruent to $0$). For any such $a$, there is a unique $b$ such that $ab\equiv -d\pmod{p}$. Then $x^2-y^2\equiv d\pmod{p}$ if and only if $x+y\equiv b\pmod{p}$.

Since $p$ is odd, $2$ is invertible modulo $p$, and therefore the system $x-y\equiv a\pmod p$, $x+y \equiv b\pmod{p}$ has a unique solution $(x,y)$ modulo $p$. It follows that there are as many solutions of the original congruence as there are choices for $a$, namely $p-1$. The case $p=3$ is not special, we can take $p \ge 3$.