How many solutions modulo prime? Let $p$ be given prime $q$ or power of prime $q^r$.
How many pairs $x \pmod p,y \pmod p$ can one expect for the equation $x^{2} - y^{2} \equiv k \pmod p$ where $k \pmod p \neq 0$ is given?
 A: We deal with the original problem that asked only about primes. 
The case $p=2$ is special, but easy to take care of. So let $p$ be an odd prime.
The case $k\equiv 0\pmod{p}$ is special, so for now assume $k\not\equiv 0\pmod{p}$.
We are looking at the congruence $(x-y)(x+y)\equiv k\pmod{p}$. Given any solution $(x,y)$, the pair $(x-y,x+y)$ is an ordered pair with product congruent to $k$. Conversely, let $(a,b)$ be an ordered pair such that $ab\equiv k\pmod{p}$. Then by solving the linear system $x-y\equiv a\pmod{p}$, $x+y\equiv b\pmod{p}$ we obtain a pair $(x,y)$ such that $x^2-y^2\equiv k\pmod{p}$. The system has a unique solution, obtained in the usual way.  
There are $p-1$ possibilities for $a$, and hence $p-1$ solutions to the original congruence.
Finally, we deal with $p$ odd, $k$ a multiple of $p$. For any $x\not\equiv 0\pmod{p}$, there are $2$ possible values of $y$. Along with $(0,0)$ this gives $2p-1$ solutions.
Remark: The same analysis works for $x^2-y^2\equiv k\pmod{n}$, where $n$ is odd and $k$ and $n$ are relatively prime. For even $n$, a small change is needed. 
Dealing with general $n$ and $k$ not relatively prime to $n$ may be messy. 
