自动搬运

查看原文

来自洛谷，原作者为

	WorldMachine 请引领我至夜晚熠熠闪烁的群星之下

搬运于2025-08-24 21:32:14，当前版本为作者最后更新于2025-05-11 21:01:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先来求模素数 $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)\mapsto\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-ρ 分解素因子计算即可。