Number of solution is twice $(x,y)$

Question

Problem: Count the number of $2 \times 2$ matrices $A$ with $A^TA=-I$ in $Z_p$ for $p>2$.

Answer: if $p$ is an odd prime, the number of such matrices $A$ is twice the number of solutions $(x,y)$ to the congruence $x^2+y^2 \equiv -1 \pmod p$.

What's the reason behind "twice"?

Answer 1

Let \begin{eqnarray*} A= \begin{bmatrix} a &b \\c &d \\ \end{bmatrix} . \end{eqnarray*} Then we require \begin{eqnarray*} \begin{bmatrix} a &c \\b &d \\ \end{bmatrix} \begin{bmatrix} a &b \\c &d \\ \end{bmatrix} = \begin{bmatrix} -1 &0 \\0 &-1 \\ \end{bmatrix} . \end{eqnarray*} So \begin{eqnarray*} a^2+c^2 \equiv -1 \pmod{p} \\ ab+cd \equiv 0 \pmod{p} \\ b^2+d^2 \equiv -1 \pmod{p} \\ \end{eqnarray*} After a little algebra with these \begin{eqnarray*} a^2b^2=b^2(-1-c^2)=c^2d^2 \\ c^2(\underbrace{d^2+b^2}_{-1})=-b^2 \end{eqnarray*} So $b=c$ or $b=p-c$. Giving two solutions for each pair $(a,c)$.

Answer 2

$$A^TA=-I$$

is equivalent to $A^{-1}=-A^T$ and hence implies $AA^T=-I$.

If $A=\begin{bmatrix} a&b \\ c&d \end{bmatrix}$ Then $$A^TA=-I \Leftrightarrow AA^T=-I \mbox{ and }A^TA=-I \\ \begin{bmatrix} a&b \\ c&d \end{bmatrix}\begin{bmatrix} a&c\\ b&d \end{bmatrix}= \begin{bmatrix} -1&0 \\ 0&-1 \end{bmatrix} \mbox{ and } \begin{bmatrix} a&c \\ b&d \end{bmatrix}\begin{bmatrix} a&b\\ c&d \end{bmatrix}= \begin{bmatrix} -1&0 \\ 0&-1 \end{bmatrix}\Leftrightarrow \\ a^2+b^2=-1 \\ c^2+d^2=-1 \\ ac+bd=0 \\ a^2+c^2=-1 \\ b^2+d^2=-1 \\ ab+cd=0 $$

Now $$a^2+b^2=-1=a^2+c^2 \Rightarrow b^2=c^2 \Rightarrow b= \pm c\\ a^2+b^2=-1=b^2+d^2 \Rightarrow a^2=d^2 \Rightarrow a= \pm d \\ $$

Using $b =\pm c$ and $a=\pm d$ in $$ac+bd=0 \\ ab+cd=0$$

you get that either $a=b=c=d=0$ or the signs in $b =\pm c$ and $a=\pm d$ are opposite.

Therefore, if you combine everything we got, the system above reduces to $$a^2+b^2=-1$$ and, either $c=-b, d=a$, or $c=b, d=-a$.