Problem: count the $2 \times 2$ matrices $A$ with $A^tA=-I$ in $Z_p$ for a fixed $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(mod p)$. Hence, for odd primes $p$, the number of such matrices $A$ is $2(p-1)$ or $2(p+1)$, according as $p \equiv 1(mod 4)$ or $p \equiv -1(mod 4)$.
Someone please clarify how it come up with $2(p-1)$ and $2(p+1)$ or show a detailed proof of this. Thanks in advance :)
Consider the curve $C$ in $\mathbb{P}^2$ defined by the equation $X^2+Y^2=-Z^2$. We wish to count the number of points $[X,Y,Z]$ on this curve over $\mathbb{Z}_p$ with $Z\neq 0$ (since those are the same as solutions to $x^2+y^2=-1$, taking $x=X/Z$ and $y=Y/Z$). We will count this by counting all the points on $C$ and then subtracting the points with $Z=0$.
First, let us show that $C$ has at least one point. If there are no two squares whose sum is $-1$ in $\mathbb{Z}_p$, then $a\mapsto -1-a$ would be an injection from the set of squares to the set of nonsquares. But there are $\frac{p+1}{2}$ squares and only $\frac{p-1}{2}$ nonsquares, so this is impossible.
So, $C$ has a point over $\mathbb{Z}_p$. Since $C$ is a conic (and is smooth since $p>2$), projection from that point gives an isomorphism $C\cong\mathbb{P}^1$ over $\mathbb{Z}_p$, so $C$ has $p+1$ points over $\mathbb{Z}_p$.
Now we count the points of $C$ with $Z=0$. These are solutions in $\mathbb{P}^1$ to $X^2+Y^2=0$. Equivalently, these are solutions to $x^2=-1$ where $x=X/Y$. If $p$ is $1$ mod $4$ then $-1$ is a square mod $p$ so there are two solutions, and if $p$ is $-1$ mod $4$ then $-1$ is not a square so there are no solutions.
So, if $p$ is $1$ mod $4$, there are $(p+1)-2=p-1$ solutions to $x^2+y^2=-1$. If $p$ is $-1$ mod $4$, there are instead $(p+1)-0=p+1$ solutions.