Number of solution is twice $(x,y)$ 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"?
 A: $$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$.
A: 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)$.
