为何Z_p(p>2)中满足A^TA=-I的2×2矩阵数是同余方程解的两倍？

让我们从拆解矩阵的条件开始。假设$A = \begin{bmatrix}a & b \ c & d\end{bmatrix}$，那么$A^T A = -I$展开后会得到三个同余条件：

• $a^2 + c^2 ≡ -1 \pmod{p}$（对应结果矩阵的左上角元素）
• $b^2 + d^2 ≡ -1 \pmod{p}$（对应右下角元素）
• $ab + cd ≡ 0 \pmod{p}$（对应两个非对角线元素，必须都是0）

首先，第一个条件$a^2 + c^2 ≡ -1$正好就是我们要的同余方程的解$(a,c)$。现在关键问题是：对于每个这样的$(a,c)$，有多少组$(b,d)$能满足后面两个条件？

我们来看第三个条件$ab + cd ≡0$，这等价于向量$(b,d)$和向量$(a,c)$在$\mathbb{Z}_p^2$中是正交的（点积为0）。在二维空间里，一个非零向量的正交补是一维子空间——所有形如$k \cdot (-c, a)$的向量（因为$(a,c) \cdot (-c,a) = -ac + ca =0$，刚好正交）。

接下来代入第二个条件$b^2 + d^2 ≡-1$。把$b=-kc$，$d=ka$代入进去：
$$(-kc)^2 + (ka)^2 = k^2(c2 + a^2) = k^2(-1)$$
我们需要这个等于$-1$，所以：
$$k^2(-1) ≡ -1 \pmod{p} \implies k^2 ≡1 \pmod{p}$$

因为$p$是奇素数，$1$和$-1$是模$p$下$k^2=1$的两个不同解（毕竟$p>2$，所以$1≠-1$）。这意味着对于每个$(a,c)$，我们有两个不同的$(b,d)$选择：

1. $k=1$时，$(b,d)=(-c,a)$，对应矩阵$\begin{bmatrix}a & -c \ c & a\end{bmatrix}$
2. $k=-1$时，$(b,d)=(c,-a)$，对应矩阵$\begin{bmatrix}a & c \ c & -a\end{bmatrix}$

而且这两个矩阵肯定是不同的——如果它们相等，会推出$a=-a$且$c=-c$，即$2a≡0$且$2c≡0$，但$p>2$，所以$a=c=0$，这和$a^2+c2=-1$矛盾，不可能成立。

另外，不同的$(a,c)$解也不会对应同一个矩阵——如果两个不同的$(a_1,c_1)$和$(a_2,c_2)$对应同一个矩阵，那它们的$a$和$c$必须分别相等，也就是同一个解。

总结一下：每个满足$x^2+y2≡-1$的解$(x,y)$，都能唯一对应两个不同的矩阵$A$满足$A^T A=-I$，反过来每个这样的矩阵也能唯一对应一个方程的解（取矩阵的第一列$(a,c)$）。所以总矩阵数量就是方程解数的两倍。

内容的提问来源于stack exchange，提问作者User432477438