Let $p$ be an odd prime, and let $a\in\mathbb{Z}_p$ such that $a\not\equiv 0$. I need to show that there are $p-1$ ordered pairs $(x,y)$ such that $x^2-y^2\equiv a \mod{p}$. As I see it, the followings cases need to be taken into account:
- If $a$ is a quadratic residue mod $p$, then we know that for some $b$, $(\pm b,0)$ are two solutions. If $p\equiv 1\mod{4}$, then $-a$ is also a quadratic residue, and therefore there are two solutions $(0,\pm c)$ where $c^2\equiv -a$. These are 4, which means there are $p-5$ more pairs to find (if $p=5$ we are done). If $p\equiv 3\mod{4}$, then $-a$ is not a quadratic residue, and therefore no solution exists with $x=0$. After these considerations, finding the rest of the solutions is equivalent of asking for which $y$'s is $y^2+a$ a quadratic residue, which is equivalent to asking for which quadratic residues $q$ is $q-a$ a quadratic residue.
- If $a$ is not a quadratic residue, then if $p\equiv 1\mod 4$ then $-a$ is also not a quadratic residue, and therefore no solutions of the form $(0,y)$ or $(x,0)$, exists, and the problem is equivalent to asking for which quadratic residues $q$ is $q-a$ a quadratic residue. If $p\equiv 3\mod{4}$, then $-a$ is a quadratic residue, and therefore two solutions exist of the form $(0,\pm b)$ where $b^2\equiv -a\mod{p}$, and finding the rest of the solutions is equivalent to asking for which quadratic residues $q$ is $q-a$ a quadratic residue.
It seems a bit clumsy with all the cases, but this is as far as I got. How can I find for which (or more helpful, for how many) quadratic residues $q$ is $q-a$ also a quadratic residue?