$x^2+y^2=-1 \mod p$ is solvable if $p \equiv 3 \mod 4$

Question

Is there an elementary proof (i.e. without using fields and norms) for the fact that for a prime $p$ the congruence $x^2+y^2=-1 \mod p$ is solvable if $p \equiv 3 \mod 4$?

Answer 1

If $p$ is a prime then $x^2$ can leave the remainders $0,1^2,2^2,\dots ,[(p-1)/2]^2$ when divided by $p$, and all of them are distinct.

Now suppose $x^2+y^2$ does not leave a remainder $p-1$ when divided by $p$ for any value of $x,y$.

So $y^2$ can't leave the remainders $(-1+0),(-1-1^2),(-1+2^2),(-1+3^2),\dots (-1+[(p-1)/2]^2)$ when divided by $p$.

Note that all of them are distinct and there are $(p+1)/2$ of them, so the cardinality of the set of remainders $y^2$ when divided by $p$ can be at most $(p-1)/2$ but we know that the cardinality of the set of remainders $y^2$ when divided by $p$ is $(p+1)/2$, hence a contradiction.

So for any prime $p$, irrespective of whether it is of the form $4k+1$ or $4k+3$, the above congruence has a solution!