(Noob question) When will $p$ divide $b^2+1$ for $b<p$?

Question

Let $p$ be a prime number and $b$ an integer so that $b<p$. For which values of $p$ and $b$ $$(p \mid b^2+1)$$? How many possible values of $b$ are there for each $p$? Is there any special "rule" for it to hold?

Answer 1

The integers mod $p$ are a finite field, so there cannot be more than two solutions to $x^2+1\equiv0$ mod $p$. If $p=2$, there is just one solution. If $p\equiv3$ mod $4$, there are no solutions, while if $p\equiv1$ mod $4$ there are two solutions. The results for $p\equiv\pm1$ mod $4$ follow from Fermat's sum-of-two squares theorem. In particular, if $p\equiv1$ mod $4$, then $p=m^2+n^2$ for some two positive integers $m$ and $n$, neither of which can be divisible by $p$ for obvious reasons, and thus we have $(\pm mn^*)^2+1\equiv0$ mod $p$, where $n^*$ is the reciprocal of $n$ mod $p$, i.e., $nn^*\equiv1$ mod $p$.