<s>[INST] 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"?
 [/INST] 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)$.
</s>