For every prime $p$, there exists $a,b \in \mathbb{Z}$ such that $p\mid a^2+b^2+1$
For context, this question shows up as a statement on a hint to showing that every positive integer is a sum of 4 squares using the Hurwitz Quaternions, I managed to solve the problem using this fact but I don't see why this fact holds at all, specifically I managed to solve it for $p=2$ or $p\equiv 1 \pmod 4$ in a trivial manner, but for the other primes I don't quite see how that would work, I assume it can be solved using some results from quadractic residues but I am not sure.
It is well known that there are exactly $\frac{p+1}{2}$ quadratic residues modulo $p$ (including $0$) for any odd prime $p$. Therefore, $a^2$ can take $\frac{p+1}{2}$ distinct values modulo $p.$ The same holds for $-b^2 - 1.$ Now, we have $p+1$ values modulo $p$ in total. By the pigeonhole principle, there is at least one pair of these values which are congruent. This observation concludes the proof.