Quadratic Congruence for every prime

The result is obvious for $p=2$, and as you point out it is straightforward for primes of the form $4k+1$. But we give a proof that works for all odd primes.

Let $A$ be the set $\left\{0^2,1^2,2^2,\dots, \left(\frac{p-1}{2}\right)^2\right\}$. Let $B$ be the set $\left\{-1-0^2, -1-1^2, -1-2^2, \dots, -1-\left(\frac{p-1}{2}\right)^2\right\}$.

It is easy to show that any two elements of $A$ are incongruent modulo $p$, as are any two elements of $B$.

But the number of elements of $A$ is $\frac{p-1}{2}+1$, as is the number of elements of $B$.

The sum of the sizes of $A$ and $B$ is $p+1\gt p$. Thus by the Pigeonhole Principle there exist $x\in A$, $y\in B$ such that $x\equiv y\pmod{p}$.

It follows that there is an $a$ and a $b$ such that $a^2\equiv -1-b^2\pmod{p}$. This is what we wanted to prove.