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^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$.
