# 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?

-
If $k\ne 0$ we can expect $n-1$ pairs per $k\pmod{p}$. I believe there's a proof using quadratic residues. –  Foo Barrigno Jul 31 '13 at 11:36
what is $n$ in your comment? –  Turbo Jul 31 '13 at 11:36
Sorru, $n = p$. I was mixing up my terminology. I think you can use the fact that if $x$ is a residue $\pmod{p}$ then $-x$ is not a residue. –  Foo Barrigno Jul 31 '13 at 11:39
If $k=0$ and $p>2$, there are $p(p-1)$ coming from $x=y$ and $x=-y$. –  Lior B-S Jul 31 '13 at 11:45
@Arul - no proof, however it holds at least for $p\le 17$ –  Foo Barrigno Jul 31 '13 at 11:50

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.

-
Same holds if $p = q^r$? with case $q=2$ also included? –  Turbo Jul 31 '13 at 12:08
For powers $q^r$ of an odd prime $q$, and $k$ not divisible by $q$, same argument gives $\varphi(q^r)$, so $(p-1)p^{r-1}$. For $k$ divisible by various powers of $q$ it gets a little messy, with odd powers and even powers behaving a bit differently. Powers of $2$ are also special. –  André Nicolas Jul 31 '13 at 12:29