If $i = \sqrt{(-1)} \bmod p$, $p$ prime, does not exist, then we can form numbers of the form $a+b i \bmod p$ with multiplicative order $p^2 - 1$. How often do these numbers occur modulo $p$? In other words, how many complex values of the form $a+b i \bmod p$, where $a$ and $b$ are taken from $\mathbb{Z} /p \mathbb{Z}$ have multiplicative order $p^2-1$?
PROBLEM RESTATEMENT
As Joanpemo points out, I'm looking for the number of elements of multiplicative order $p^2 - 1$ in the field $\mathbb{F}_{p^2}$ with $p \equiv 3 \bmod 4$, and $p$ prime.
If we're talking of the field $\;\Bbb F_{p^2}\;$ , then the multiplicative group of this, $\;\left(\Bbb F_{p^2}\right)^*:=\Bbb F_{p^2}\setminus\{0\}\;$ is a cyclic group (as is any finite subgroup of the multiplicative group of any field), and in this case it is a group of order $\;p^2-1\;$ , so you're looking for the number of generators this group has, and this number is exactly $\;\phi(p^2-1)\;,\;\;\phi=$ Euler's Totient Function..
Thus, you can search in the net for asymptotics of Euler's Function, or perhaps only take this function as it is.