整数模n乘法群

在同余理论中，模 n 的互质同余类组成一个乘法群，称为整数模 n 乘法群，也称为模 n 既约剩余类。在环理论中，一个抽象代数的分支，也称这个群为整数模 n 的环的单位群（单位是指乘法可逆元）。

这个群是数论的基石，在密码学、整数分解和素性测试均有运用。例如，关于这个群的阶（即群的“大小”），我们可以确定如果 n 是质数当且仅当阶数为 n-1。

## 群公理

容易验证模 n 互质同余类在乘法运算下满足阿贝尔群的公理。

互质同余类的乘法是良好定义：a 与 n 互质，当且仅当 gcd(a, n) = 1. 同余类中的整数a ≡ b (mod n) 满足gcd(a, n) = gcd(b, n), 因此一个整数与 n 互质当且仅当另一个整数也与 n 互质.

恒同: 1 是恒同； 1所在的同余类是唯一的乘法恒同类

闭：如果 a 和 b 都与 n 互质，那么 ab 也是；因为gcd(a, n) = 1 与 gcd(b, n) = 1 意味着 gcd(ab, n) = 1, 与 n 互质的同余类在乘法下是封闭的。

逆：找 x 满足 ax ≡ 1 (mod n) 等价于解 ax + ny = 1，可用欧几里得算法求出x，并且x在模n的同余类里。当 a 与 n 互质, 由于 gcd(a, n) = 1 ,根据 裴蜀定理 存在整数 x 与 y 满足 ax + ny = 1. 注意到由等式 ax + ny = 1 可推出 x 与 n 互质, 所以乘法逆元属于群.

结合性和交换性：由整数的相应事实以及模 n 运算是一个环同态推出。由于同余类a ≡ a' 与 b ≡ b' (mod n) 的整数乘法意味着 ab ≡ a'b' (mod n). 这可推出乘法满足结合律、交换律。

## 记法

整数模 n 环记作 $\mathbb{Z}/n\mathbb{Z}$ 或 $\mathbb{Z}/(n)$（即整数环模去理想 nZ = (n)，由 n 的倍数组成）或 $\mathbb{Z}_n.$ 因作者所喜，它的单位群可能记为 $(\mathbb{Z}/n\mathbb{Z})^*,$ $(\mathbb{Z}/n\mathbb{Z})^\times,$ $U(\mathbb{Z}/n\mathbb{Z}),$ 或类似的记号，本文采用 $(\mathbb{Z}/n\mathbb{Z})^\times.$

## 结构

### 2 的幂次

模 2 只有一个互质同余类 1，所以$(\mathbb{Z}/2\mathbb{Z})^\times \cong \{1\}$ 平凡。

模 4 有两个互质同余类，1 和 3，所以 $(\mathbb{Z}/4\mathbb{Z})^\times \cong C_2,$ 两元循环群。

模 8 有四个互质同余类，1, 3, 5 和 7，每个平方都是 1，所以 $(\mathbb{Z}/8\mathbb{Z})^\times \cong C_2 \times C_2,$ Klein 四元群。

模 16 有八个互质同余类，1, 3, 5, 7, 9, 11, 13 和 15。$\{\pm 1, \pm 7\}\cong C_2 \times C_2,$ 为 2-扭子群（即每个元素的平方为 1），所以 $(\mathbb{Z}/16\mathbb{Z})^\times$ 不是循环群。3的幂次：$\{1, 3, 9, 11\}$ 是一个 4 阶子群，5 的幂次也是，$\{1, 5, 9, 13\}$。所以 $(\mathbb{Z}/16\mathbb{Z})^\times \cong C_2 \times C_4$。

以上 8 和 16 的讨论对高阶幂次 2k, k > 2 也成立：

$\{\pm 1, 2^{ k-1} \pm 1\}\cong C_2 \times C_2,$ 是 2-扭子群（所以 $(\mathbb{Z}/2^k\mathbb{Z})^\times$ 不是循环）而 3 的幂次是一个2k- 2 子群，所以 $(\mathbb{Z}/2^k\mathbb{Z})^\times \cong C_2 \times C_{2^{k-2}}$。

### 奇质数的幂

对奇质数的幂 pk，此群是循环群： $\;\;(\mathbb{Z}/p^k\mathbb{Z})^\times \cong C_{p^{k-1}(p-1)} \cong C_{\varphi(p^k)}.$

### 一般合数

中国剩余定理 说明如果$\;\;n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots, \;$ 那么环 $\mathbb{Z}/n\mathbb{Z}$ 每个质数幂因子相应的环的直积：

$$\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/{p_1^{k_1}}\mathbb{Z}\; \times \;\mathbb{Z}/{p_2^{k_2}}\mathbb{Z} \;\times\; \mathbb{Z}/{p_3^{k_3}}\mathbb{Z}\dots\;\;$$

类似地，$(\mathbb{Z}/n\mathbb{Z})^\times$ 的单位群是每个质数幂因子相应群的直积：

$$(\mathbb{Z}/n\mathbb{Z})^\times\cong (\mathbb{Z}/{p_1^{k_1}}\mathbb{Z})^\times \times (\mathbb{Z}/{p_2^{k_2}}\mathbb{Z})^\times \times (\mathbb{Z}/{p_3^{k_3}}\mathbb{Z})^\times \dots\;.$$

## 阶数

群的阶数由欧拉函数给出：$| (\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n).$ 这是直积中各循环阶数的乘积。

## 指数

指数为卡迈克尔函数$\lambda(n)$，即这些循环群的阶数的最小公倍数。这意味着如果 a 和 n 互质，$a^{\lambda(n)} \equiv 1 \pmod n.$

## 生成元

$(\mathbb{Z}/n\mathbb{Z})^\times$ 是循环群当且仅当 $\varphi(n)=\lambda(n).$ 这在 n 为奇质数的幂次、奇质数幂次 2 倍、2 和 4 成立，此时也称一个生成元为模 n 的原根。

因为所有 $(\mathbb{Z}/n\mathbb{Z})^\times,$ n = 1, 2, ..., 7 是循环群，上述结论的另一种说法是：如果 n < 8 那么 $\;(\mathbb{Z}/n\mathbb{Z})^\times$ 有原根；如果 n ≥ 8，且不能被 4 或者两个不同的奇质数整除，$\;(\mathbb{Z}/n\mathbb{Z})^\times$ 有原根。( = 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, 22, 23, 25, 26, 27, 29, 31, 34, 37, 38, 41, 43, 46, 47, 49, 50, ... )

一般情形每个直积因子循环有一个生成元。

## 列表

这个表列出了较小 n $(\mathbb{Z}/n\mathbb{Z})^\times$ 的结构和生成元。生成元不是惟一（mod n）的，比如 (mod 16) 时 {–1, 3} 和{–1, 5} 都可以。生成元以和直积因子相同的顺序列出。

以 n=20 为例。$\varphi(20)=8$ 意味着 $(\mathbb{Z}/20\mathbb{Z})^\times$ 的阶数是 8（即有 8 个小于 20 的正整数与其互质）；$\lambda(20)=4$ 说明任何和20互质的数的 4 次幂≡ 1(mod 20)；至于生成元，19 的指数为2，3 的指数为 4，而任何$(\mathbb{Z}/20\mathbb{Z})^\times$ 中元素都是 19a × 3b 的形式，这里 a 为 0 或 1，b 为 0, 1, 2, 或 3。

19 的幂是 {±1}，3 的幂为 {3, 9, 7, 1}。后者和他们的负数 (mod 20)，{17, 11, 13, 19} 是所有小于 20 且与其互质的数。19 的指数为 2 而 3 的指数为 4 意味着任何 $\mathbb{Z}_{20}^\times$ 中数的 4 次幂 ≡ 1 (mod 20)。

$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\lambda(n)$｜生成元｜ ｜$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\lambda(n)$｜生成元｜ ｜$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\lambda(n)$｜生成元

1｜C1｜1｜1｜0｜32｜C2×C8｜16｜8｜31, 3｜63｜C6×C6｜36｜6｜2, 5

2｜C1｜1｜1｜1｜33｜C2×C10｜20｜10｜10, 2｜64｜C2×C16｜32｜16｜3, 63

3｜C2｜2｜2｜2｜34｜C16｜16｜16｜3｜65｜C4×C12｜48｜12｜2, 12

4｜C2｜2｜2｜3｜35｜C2×C12｜24｜12｜6, 2｜66｜C2×C10｜20｜10｜5, 7

5｜C4｜4｜4｜2｜36｜C2×C6｜12｜6｜19, 5｜67｜C66｜66｜66｜2

6｜C2｜2｜2｜5｜37｜C36｜36｜36｜2｜68｜C2×C16｜32｜16｜3, 67

7｜C6｜6｜6｜3｜38｜C18｜18｜18｜3｜69｜C2×C22｜44｜22｜2, 68

8｜C2×C2｜4｜2｜7, 3｜39｜C2×C12｜24｜12｜38, 2｜70｜C2×C12｜24｜12｜3, 11

9｜C6｜6｜6｜2｜40｜C2×C2×C4｜16｜4｜39, 11, 3｜71｜C70｜70｜70｜7

10｜C4｜4｜4｜3｜41｜C40｜40｜40｜6｜72｜C2×C2×C6｜24｜12｜5, 7, 11

11｜C10｜10｜10｜2｜42｜C2×C6｜12｜6｜13, 5｜73｜C72｜72｜72｜5

12｜C2×C2｜4｜2｜5, 7｜43｜C42｜42｜42｜3｜74｜C36｜36｜36｜5

13｜C12｜12｜12｜2｜44｜C2×C10｜20｜10｜43, 3｜75｜C2×C20｜40｜20｜2, 74

14｜C6｜6｜6｜3｜45｜C2×C12｜24｜12｜44, 2｜76｜C2×C18｜36｜18｜3, 75

15｜C2×C4｜8｜4｜14, 2｜46｜C22｜22｜22｜5｜77｜C2×C30｜60｜30｜2, 76

16｜C2×C4｜8｜4｜15, 3｜47｜C46｜46｜46｜5｜78｜C2×C12｜24｜12｜5, 7

17｜C16｜16｜16｜3｜48｜C2×C2×C4｜16｜4｜47, 7, 5｜79｜C78｜78｜78｜3

18｜C6｜6｜6｜5｜49｜C42｜42｜42｜3｜80｜C2×C4×C4｜32｜4｜3, 7, 11

19｜C18｜18｜18｜2｜50｜C20｜20｜20｜3｜81｜C54｜54｜54｜2

20｜C2×C4｜8｜4｜19, 3｜51｜C2×C16｜32｜16｜50, 5｜82｜C40｜40｜40｜7

21｜C2×C6｜12｜6｜20, 2｜52｜C2×C12｜24｜12｜51, 7｜83｜C82｜82｜82｜2

22｜C10｜10｜10｜7｜53｜C52｜52｜52｜2｜84｜C2×C2×C6｜24｜12｜5, 11, 13

23｜C22｜22｜22｜5｜54｜C18｜18｜18｜5｜85｜C4×C16｜64｜16｜2, 3

24｜C2×C2×C2｜8｜2｜5, 7, 13｜55｜C2×C20｜40｜20｜21, 2｜86｜C42｜42｜42｜3

25｜C20｜20｜20｜2｜56｜C2×C2×C6｜24｜6｜13, 29, 3｜87｜C2×C28｜56｜28｜2, 86

26｜C12｜12｜12｜7｜57｜C2×C18｜36｜18｜20, 2｜88｜C2×C2×C10｜40｜10｜3, 5, 7

27｜C18｜18｜18｜2｜58｜C28｜28｜28｜3｜89｜C88｜88｜88｜3

28｜C2×C6｜12｜6｜13, 3｜59｜C58｜58｜58｜2｜90｜C2×C12｜24｜12｜7, 11

29｜C28｜28｜28｜2｜60｜C2×C2×C4｜16｜4｜11, 19, 7｜91｜C6×C12｜72｜12｜2, 3

30｜C2×C4｜8｜4｜11, 7｜61｜C60｜60｜60｜2｜92｜C2×C22｜44｜22｜3, 91

31｜C30｜30｜30｜3｜62｜C30｜30｜30｜3｜93｜C2×C30｜60｜30｜5, 11

## 参见

- Lenstra 椭圆曲线分解，Lenstra给出的基于椭圆曲线的整数因子分解算法。

## 参考文献

高斯的算术研究（Disquisitiones Arithemeticae）由古典拉丁语翻译成英语和德语。德语版包含他所有数论的论文：所有关于二次互反律的证明，高斯和符号的确定，双二次互反律的研究以及未发表的笔记。