By completing the square mod $p$ (using that $p$ is odd), we may assume that $a=b=0$ so that we want $p \mid x^2+y^2+c$. Write this as $x^2 \equiv -y^2-c$ and note that both sides take $\frac{p+1}{2}$ different values modulo $p$ (by the count of quadratic residues) so that we are done by the Pigeonhole Principle.

You can't just assume $a=b=0$. $a$ and $b$ are given integers

Bexultan wrote: You can't just assume $a=b=0$. $a$ and $b$ are given integers Huh? Did you even read my post? Of course $a$ and $b$ are given but we can always replace $x$ with $x+\frac{a}{2}$ and hence w.l.o.g. assume that $a=b=0$ (i.e. we reduce the case of general $a,b$ to the special case $a=b=0$).

Doesn’t that only work if $a/2$ is an integer?

FFAmplify wrote: Doesn’t that only work if $a/2$ is an integer? $a \cdot 2^{-1} (2 \cdot 2^{-1} \equiv 1 \pmod p)$

FFAmplify wrote: Doesn’t that only work if $a/2$ is an integer? This is a valid point, but this is exactly why I mentioned that $p$ is odd at that point since this allows us to divide by $2$ modulo $p$. In more concrete terms, if $a$ is even you can use $\frac{a}{2}$ and if $a$ is odd you can use $\frac{a+p}{2}$.