Let $p$ be a prime number. Prove that exists $a,b \in \mathbb{Z}$ such that $p|a^2+b^2+1$. What I've tried:
If $p \equiv 1 \mod 4$, we put $b=0$ and the condition is simply $a^2 \equiv -1 \mod p$ which has a solution by basic quadratic reprocity.
If $p \equiv 3 \mod 4$, I did not see anything simple that might work and some examples don't show any apparent pattern ($7|3^2+2^2+1,$ $19|6^2+1^2+1$, $23 | 6^2+3^2+1$, etc.)
Thank you.
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.
