Show that the number of solutions of $x^2+y^2 ≡ 1$ (mod $p$) where $0Show that the number of solutions of $x^2+y^2 ≡ 1$ (mod $p$) where $0<x<p$, $0<y<p$, $p$ is odd prime is even iff $p ≡ 3, -3$ (mod $8$).
I learned about quadratic residue and sums of squares.
Let
$S_1$ = {$1^2, 2^2, ... , (p-1)^2$}
$S_2$ = {$1-1^2, 1-2^2, ... , 1-(p-1)^2$}.
No two element of the set $S_1$, $S_2$ are congruent modulo $p$.
Together $S_1$, $S_2$ contain $2p-2$ integers.
By the pigeonhole principle, there exist $x_0$, $y_0$ such that 
$x_0^2$ ≡ $1-y_0^2$ (mod $p$).
But I don't know how to continue.

If $(x,y)$ is a solution, so are $(\pm x, \pm y)$, and since $p$ is odd, all $4$ solutions are distinct, mod $p$.

Hence the number of solutions is a multiple of $4$.

Note:$\;$For this argument, $p$ can be any odd positive integer, not necessarily prime.
