Number of matrices on $\mathbb Z_{p}$ with a given characteristic polynomial

$\newcommand{\Size}[1]{\left\lvert #1 \right\rvert}$For your special case, with characteristic polynomial $x^{2} + 1$ and $p \equiv 3 \pmod{4}$, the matrix is conjugate to its rational canonical form $$ R = \begin{bmatrix} 0 & 1\\ -1 & 0\\ \end{bmatrix}. $$ So it is just a matter to see how many conjugates $R$ has. Alternatively, one may compute the centralizer of $R$, and discover that it is $$ a I + b R $$ with $a, b$ not both zero. So the centralizer has order $p^2 - 1$, hence $R$ has $$\dfrac{\Size{\operatorname{GL}(2,p)}}{p^2 - 1} = \dfrac{(p^{2} - 1)(p^{2} - p)}{p^2 - 1} = p(p-1)$$ conjugates.

When $p \equiv 1 \pmod{p}$, then the matrix can be put in the form $$ R = \begin{bmatrix} a & 0\\ 0 & -a\\ \end{bmatrix}. $$ where $a$ is a primitive fourth root of unity. This time the centralizer has order $(p-1)^{2}$, as it consists of the diagonal matrices, hence $R$ has $$\dfrac{\Size{\operatorname{GL}(2,p)}}{(p - 1)^{2}} = \dfrac{(p^{2} - 1)(p^{2} - p)}{(p - 1)^{2}} = p(p+1)$$ conjugates.

For the characteristic polynomial $x^2-1$:

Observe that the matrices must have the form $\begin{pmatrix}a&b\\c&-a\end{pmatrix}$ where $$a^2=1-bc.$$ Hence, given $b$ and $c$ we can find zero, one or two $a$'s that will work. To count the number of solutions, we consider the following cases:

• If $1-bc=0$. In this case there's only one $a$ (namely $a=0$) that will work. Give a non-zero $c$, and there's only one $b$, namely $b=1/c$ (and of course, $c=0$ doesn't work). Conclusion: there are $p-1$ such matrices with $bc=1$.

• If $1-bc=1$, i.e., $bc=0$. In this case there are two $a$'s that will work (except if $p=2$). Now, to have $bc=0$ we consider the number of possible pairs $(b,c)$:

  • $b=0,c\neq0$: there are $p-1$ pairs ($p-1$ possible $c$'s),
  • dually, $b\neq0,c=0$ yields $p-1$ pairs,
  • $b=0,c=0$: only one possibility

  Hence this case yields $2p-1$ pairs hence we'll have $4p-2$ corresponding matrices if $p\neq2$ (and $2p-1=3$ if $p=2$).

• If $1-bc\not\in\{0,1\}$ (case only valid if $p\neq2$): we know that there are $(p-1)/2$ quadratic residues modulo $p$; we already considered one (namely, $1$) so there are $(p-3)/2$ quadratic residues left. For each of them, say $q\neq1$, there are $(p-1)$ pairs $(b,c)$ such that $1-bc=q$, namely $c\neq0$ and $b=(1-q)/c$: that's only one $b$ for each non-zero $c$, hence $(p-1)$ number of pairs $(b,c)$. There are exactly two $a$'s in this case. Hence there are exactly $(p-3)(p-1)$ such matrices with $1-bc\not\in\{0,1\}$.

Conclusion: if $p=2$ we have $4$ such matrices and if $p\neq2$ there are $$p-1+4p-2+(p-3)(p-1)=p(p+1)$$ such matrices. Moreover, the proof is constructive.

For the characteristic polynomial $x^2+1$: notice that the previous proof can be adapted as follows: the equation characterizing the matrices is $a^2=-1-bc$. The case $p=2$ is similar to the previous one, so we exclude it.

• If $-1-bc=0$: $p-1$ matrices,
• If $-1-bc=-1$: $2p-1$ pairs $(b,c)$, but $-1$ is a quadratic residue if and only if $p=1\pmod4$. This amounts for $4p-2$ matrices if $p=1\pmod4$ and $0$ otherwise;
• If $-1-bc\not\in\{0,-1\}$: $(p-1)$ pairs $(b,c)$ for a given $-1-bc$; there are $(p-1)/2$ quadratic residues, one was already considered in the previous case when $p=1\ (\text{mod}4)$. There are $2$ corresponding $a$'s. This amounts to $(p-3)(p-1)$ matrices if $p=1\ (\text{mod}4)$ and $(p-1)^2$ if $p=3\pmod4$.

Conclusion: there are that many such matrices: $$\begin{cases} p(p-1)&\text{if $p=3\pmod4$}\\ p(p+1)&\text{if $p=1\pmod4$}. \end{cases}$$