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

I learned about quadratic residue and sums of squares.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.