# Show 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$)

Show 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$).

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.