题解：P1951 [Aboi 2077] SL2(Z/NZ)

· · 题解

首先来求模素数 p 意义下行列式为 1 的 2\times 2 矩阵个数，即 |\text{SL}_2(\mathbb Z/p\mathbb Z)|。注意到可以通过给矩阵的某一行乘上 k 使得它的行列式变为原来的 k 倍，那么在模 p 意义下，行列式为 1 的矩阵和行列式为 k 的矩阵是一一对应的。记 |\text{GL}_2(\mathbb Z/p\mathbb Z)| 为模 p 意义下 2\times2 的可逆矩阵（行列式不为 0）的个数，有：

|\text{SL}_2(\mathbb Z/p\mathbb Z)|=\dfrac{|\text{GL}_2(\mathbb Z/p\mathbb Z)|}{p-1}

现在要求模 p 意义下行列式不为 0 的 2\times 2 矩阵个数，这就要求矩阵是满秩的，也即第一行和第二行线性无关。让第一行随便选，只要不全为 0 即可，有 p^2-1 种选法；第二行还要求不能和第一行线性相关，即不能等于 kr_1 的形式，k 可以取 0\sim p-1，一共有 p^2-p 种选法。故有 |\text{GL}_2(\mathbb Z/p\mathbb Z)|=(p^2-1)(p^2-p)，则 |\text{SL}_2(\mathbb Z/p\mathbb Z)|=p^3\left(1-\dfrac{1}{p^2}\right)。

现在要求解 \text{SL}_2(\mathbb Z/p^k\mathbb Z) 的大小，考虑如何从 p^{k-1} 推到 p^k。对于模 p^k 意义下的矩阵，将它的每个元素对 p^{k-1} 取模，可以得到群同态 f:\text{SL}_2(\mathbb Z/p^k\mathbb Z)\rightarrow\text{SL}_2(\mathbb Z/p^{k-1}\mathbb Z)，并且这是一个满同态。根据群同态基本定理，有 \dfrac{|\text{SL}_2(\mathbb Z/p^k\mathbb Z)|}{|\ker f|}=|\text{SL}_2(\mathbb Z/p^{k-1}\mathbb Z)|，那么现在要求 f 的核的大小，也就是有多少个模 p^{k-1} 意义下的单位矩阵在模 p^k 意义下行列式为 1。

设该矩阵为 \begin{bmatrix}ap^{k-1}+1&bp^{k-1}\\cp^{k-1}&dp^{k-1}+1\end{bmatrix}，其中有 0\le a,b,c,d<p。其行列式为 (ap^{k-1}+1)(dp^{k-1}+1)-bcp^{2k-2}，对 p^k 取模后为 (a+d)p^{k-1}+1，要使得其同余于 1，需要 p\mid(a+d)，满足条件的矩阵共有 p^3 个，因此有 |\ker f|=p^3。那么 |\text{SL}_2(\mathbb Z/p^k\mathbb Z)|=p^3|\text{SL}_2(\mathbb Z/p^{k-1}\mathbb Z)|。边界情况为 |\text{SL}_2(\mathbb Z/p\mathbb Z)|=p^3\left(1-\dfrac{1}{p^2}\right)，那么有：

|\text{SL}_2(\mathbb Z/p^k\mathbb Z)|=p^{3k}\left(1-\dfrac{1}{p^2}\right)

最后要对任意的 N 求出 \text{SL}_2(\mathbb Z/N\mathbb Z)。根据环论中的中国剩余定理，有环同构 \mathbb Z/N\mathbb Z\cong\prod\limits_{p^k||N}\mathbb Z/p^k\mathbb Z（p^k\mid\mid N 表示 p^k\mid N 且 p^{k+1}\nmid N）。因此有群同构：

\text{SL}_2(\mathbb Z/N\mathbb Z)\cong\prod_{p^k||N}\text{SL}_2(\mathbb Z/p^k\mathbb Z)

那么 |\text{SL}_2(\mathbb Z/N\mathbb Z)| 是积性函数，因此有：

|\text{SL}_2(\mathbb Z/N\mathbb Z)|=\prod_{p^k||N}p^{3k}\left(1-\dfrac{1}{p^2}\right)

Pollard-ρ 分解素因子计算即可。