By calculating directly show that the number of solutions to $\displaystyle x^2-y^2 \equiv a \mod{p}$ is $\displaystyle p-1$ if $\displaystyle p \nmid a$ and $\displaystyle 2p-1$ if $\displaystyle p \mid a$. (Hint: Use the change of variables $\displaystyle u = x+y$ and $\displaystyle v = x-y$.)

• Case $\displaystyle p\not|a$

First, note that the mapping $\displaystyle \left( {x,y} \right) \mapsto \left( {u,v} \right)$ is invertible. Further if $\displaystyle p\not|a$ then $\displaystyle u$ and $\displaystyle v$ are coprime to $\displaystyle p$ since we have $\displaystyle u\cdot v \equiv{a}(\bmod.p)$

Let $\displaystyle g$ be a primitive root module $\displaystyle p$ ( $\displaystyle p$ refers to a prime), then $\displaystyle u \equiv g^s \left( {\bmod .p} \right);{\text{ }}v \equiv g^t \left( {\bmod .p} \right)$ for some s and t with $\displaystyle 1\leq s,t\leq{p-1}$ since we want the incongruent solutions, so $\displaystyle g^{s + t} \equiv a\left( {\bmod .p} \right)$ here note that for each $\displaystyle s=1,...,p-1$ you have a unique $\displaystyle 0<t<p$ such that that happens. So we have p-1 incongruent solutions $\displaystyle (u,v)$ module $\displaystyle p$

Now you may check easily that the solutions $\displaystyle \left( {x,y} \right)$ are incongruent mod p if and only if the correspoding solutions$\displaystyle (u,v)$ are incongruent (with $\displaystyle p>2$ ) hence we have $\displaystyle p-1$ incogruent solutions.

• Case $\displaystyle p|a$

$\displaystyle p\left| {\left[ {\left( {x - y} \right) \cdot \left( {x + y} \right)} \right]} \right. \Rightarrow p\left| {\left( {x - y} \right)} \right. \vee p\left| {\left( {x + y} \right)} \right.$ (because $\displaystyle p$ is prime)

If $\displaystyle x\equiv{0}(\bmod.p)$ then we must have $\displaystyle y\equiv{0}(\bmod.p)$

Otherwsie, for each $\displaystyle x\not\equiv{0}(\bmod.p)$ we have $\displaystyle (x,x)$ and $\displaystyle (x,-x)$ as incongruent solutions. (again we must have $\displaystyle p>2$)

So we have: $\displaystyle 1 + 2 \cdot \left( {p - 1} \right) = 2p - 1$ solutions

Just in case, I say that 2 solutions to our equation $\displaystyle \left( {x_1,y_1} \right)$ and $\displaystyle \left( {x_2,y_2} \right)$ are incongruent mod. p if and only if $\displaystyle x_1 \equiv x_2 \left( {\bmod .p} \right)$ and $\displaystyle y_1 \equiv y_2 \left( {\bmod .p} \right)$ do not hold simultaneously