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

So I am reading "A Classical Introduction to Modern Number Theory", and I need help for one question:

Show that $$x^2 \equiv y^2-d \pmod p$$ has $p-1$ solutions for $\gcd(p,d)=1$ and $2p-1$ for $\gcd(p,d)>1$, where $p$ is a prime number greater than 3.

I am a little confused, should the answer both be $2p-1$?

-
What is $gcd(p,d)$ in the second instance? 2? >1? –  Ross Millikan Nov 1 '11 at 3:07
Oh, sorry, it should be >1 –  Rob Nov 1 '11 at 3:14

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$.