Help solving the following equation 
I'm trying to solve $a^2+b^2 \equiv -1 \bmod p$ where $a,b \in \{0,1,\dots, \frac{p-1}{2}\}$ and $p$ is an odd prime. 

I am happy with the case when $p \equiv 1 \bmod 4$ as this appears to be a fairly standard result from number theory with $b=0$. However, I am not sure how to solve it in the case when $p \equiv 3 \bmod 4$. I think I want to rearrange it somehow to relate to the previous case but am unsure how to do this. Any suggestions?
 A: For $p\equiv -1 \pmod 4$ we just need to prove that there is a non-residue which is one greater than a residue.  To see that, let $n$ be a non-residue and $r$ a residue with $r\equiv n-1 \pmod p$.  Then we remark that we may write $r\equiv a^2$ and $n\equiv -b^2\pmod p$  (where we have used the fact that $-1$ is not a residue.)  We'd then have $a^2+b^2\equiv -1\pmod p$ as desired.
To see that $n$ and $r$ exist, just remark that $1$ is a residue...so just $n$ be the smallest non-residue in $\{1,2,3,\cdots\}$ (and of course let $r=n-1$).
Examples:  $p=43$.  We easily verify that $2$ is a non-residue $\pmod {43}$.  We extract the square root of $-2\equiv 41$ and we discover that $27^2\equiv -2\pmod {43}$.  Thus we are lead to the solution $$1^2+27^2\equiv -1\pmod {43}$$  Of course, you are still forced to extract a square root to carry this out explicitly.  Also worth remarking that, if $p\equiv 3 \pmod 8$ then $2$ is not a residue so we simply have to extract the square root of $-2$ to solve the problem.
Perhaps a more interesting example is $p=47$.  Then $1,2,3,4$ are all residues, and the smallest non-residue is $n=5$.  We compute that $18^2\equiv -5\pmod {47}$ and of course $4=2^2$ so we arrive at the solution $$18^2+2^2\equiv -1\pmod {47}$$
