# Math Help - Quadratic residues

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

• Case $p\not|a$

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

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

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

• Case $p|a$

$
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 $p$ is prime)

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

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

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

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

$
do not hold simultaneously