# If $p$ is an odd prime and $D$ an integer not divisible by $p$, show that $x^2 - y^2 \equiv D ~ (\text{mod} ~ p)$ has $(p - 1)$ solutions.

I am supposed to have proved the following congruence identity: $$1^{n} + 2^{n} + \cdots + (p - 1)^{n} \equiv 0 ~ (\text{mod} ~ p).$$ This is apparently meant to help me solve the problem stated in the title. I have noticed that $$y^{2} \equiv x^{2} - D ~ (\text{mod} ~ p)$$ has solutions if and only if $x^{2} - D$ is a quadratic residue modulo $p$. I have applied the Legendre symbol to show that it is equivalent to $(x^{2} - D)^{(p - 1) / 2} ~ (\text{mod} ~ p)$. I know that I have to apply the Binomial Theorem to this, but I am not sure how. Even if I were sure, I still would not know how to produce $(p - 1)$ solutions.

I can get the number $p - 1$ based on the fact there are $(p - 1) / 2$ squares in the group $(\Bbb{Z} / p \Bbb{Z})^{*}$ and that there are two solutions for each one, but that is not the point. :/

## 2 Answers

We are looking for solutions of the congruence $x^2-y^2\equiv D\pmod{p}$, or equivalently $$(x-y)(x+y)\equiv D\pmod{p}.\tag{1}$$

Let $a$ be any of $1,2,3,\dots,p-1$, and let $b$ be the modular inverse of $a$. Consider the system of congruences $$x-y\equiv aD\pmod{p}, \quad x+y\equiv b\pmod p.$$ Since $p$ is odd, this system has a solution $(x,y)$, and that is a solution of the congruence (1).

Moreover, all solutions of (1) arise in this way, for if $(x,y)$ is a solution we can define $a$ by $x-y\equiv aD\pmod{p}$.

Hint $\$ A couple bijective transformations reduce the equation to a simpler form

$\qquad \overbrace{(x-y)}^{X}\overbrace{(x+y)}^{Y} \equiv D \iff XY \equiv D\iff X\bar Y = 1\ \ \ [\ {\rm for}\ \ \bar Y \equiv YD^{-1}]$

The solution set of $\,X\bar Y = 1\,$ is $\ (X,\bar Y) \equiv (u,u^{-1})$ for all units $\,u,\,$ i.e all $\,u\not\equiv 0$