模 n 单位群：先拆结构，再做统计

当问题要求 $a^k\equiv1\pmod n$ 的最小正整数 $k$，先检查 $\gcd(a,n)$。以下讨论 $n>1$；模 $1$ 的边界应按题目定义单独处理。

从同余转到单位群 #

若 $\gcd(a,n)>1$，公共素因子 $p$ 会使 $a^k$ 模 $p$ 等于 $0$，不可能等于 $1$。若 $\gcd(a,n)=1$，由 Bézout 等式可知 $a$ 有模 $n$ 逆元。

这些可逆剩余类组成单位群

$$U(n)=(\mathbb Z/n\mathbb Z)^\times,\qquad |U(n)|=\varphi(n).$$

在有限群中元素阶存在，且整除群的大小。因此 Euler 定理给出 $a^{\varphi(n)}\equiv1\pmod n$，但 $\varphi(n)$ 通常不是 $a$ 的最小正周期。

例如 $n=8,a=3$ 时，$\varphi(8)=4$，但 $3^2\equiv1\pmod8$，所以 $3$ 的阶是 $2$。

按素数幂分解的规则 #

设 $n=\prod_i p_i^{e_i}$。中国剩余定理保持乘法运算，并将可逆元对应到各分量的可逆元，所以

$$U(n)\cong\prod_i U(p_i^{e_i}).$$

记 $C_m$ 为 $m$ 阶循环群，需要使用的结构如下。

模数	单位群
奇素数幂 $p^e$	$C_{p^{e-1}(p-1)}$
$2$	平凡群
$4$	$C_2$
$2^e$，$e\ge3$	$C_2\times C_{2^{e-2}}$

这里奇素数幂的结论来自原根存在定理；不能只由单位个数推出它是循环群。CRT 与单位群结构的来源见完整题解中的定理与引用。

对于 $e\ge3$，模 $2^e$ 的两个生成方向可以取 $-1$ 和 $5$：前者阶为 $2$，后者阶为 $2^{e-2}$。$5$ 的幂模 $4$ 总为 $1$，不会等于 $-1$，两个子群交集只有单位元。乘积大小为 $2^{e-1}=\varphi(2^e)$，恰好覆盖全部单位。

典型例题：模 8 与模 15 #

$U(8)=\{1,3,5,7\}$。后三个元素平方都为 $1$，阶分布为一个 $1$ 和三个 $2$；故它是 $C_2\times C_2$，不能当作 $C_4$。元素阶之和为 $7$，不是 $11$。

再看 $15=3\cdot5$：

$$U(15)\cong U(3)\times U(5)\cong C_2\times C_4.$$

阶整除 $2$ 的元素有 $2\cdot2=4$ 个，其中一个是单位元，所以阶恰为 $2$ 的有 $3$ 个。全部 $8$ 个元素的阶都整除 $4$，剩下 $4$ 个阶为 $4$。阶之和为

$$1+3\cdot2+4\cdot4=23.$$

Trick：模数互素不等于答案积性 #

记 $A(n)$ 为 $U(n)$ 中所有元素的阶之和。虽然 $3$ 与 $5$ 互素，但两个单位群中的元素阶可能共享素因子。直积中的阶取最小公倍数，不能直接将两个阶之和相乘：

$$A(3)=3,\qquad A(5)=11,\qquad A(15)=23\ne33.$$

要让阶能够相乘，须把循环群长度再拆成素数幂，把同一素数的部分归为一个分量。不同素数分量中元素的阶才两两互素。

例如 $U(27)\cong C_{18}\cong C_2\times C_9$，这时可以分开统计两个素数分量，再乘起来；$C_2\times C_4$ 则必须归入同一个 $2$ 分量。

接到实现 #

E · Exponent 的 C++17 实现先分解模数，按上表得到循环群长度，再分解长度并统计各素数分量。它不需要实际寻找原根，也不枚举全部可逆元。

该实现适用于题目范围 $1\le n\le10^9$；使用 64 位整数，$n=1$ 按原题定义返回 $1$。完整题解包含推导、分解复杂度与中间乘积界，运行说明和验证摘要与同一份源码对应。

继续阅读与来源 #

• 元素阶手册条目：周期、整除与计数。
• 抽象代数：群元素的阶：数学背景。
• Exponent 的单位群分解与引用：CRT、原根及 2 的幂的结构依据。
• OI Wiki · 数论：扩展参考。

返回个人知识手册 · 第二场记录