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

结构

2 的幂次

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

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

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

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

以上 8 和 16 的讨论对高阶幂次 2^k, k > 2^[1] 也成立： ${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong C_{2}\times C_{2},}$  是 2-扭子群（所以 ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$  不是循环）而 3 的幂次是一个2^{k- 2} 子群，所以 ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong C_{2}\times C_{2^{k-2}}}$ 。

奇质数的幂

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

一般合数

中国剩余定理^[3] 说明如果${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$  那么环 ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$  每个质数幂因子相应的环的直积：

${\displaystyle \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 \;\;}$ 

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

${\displaystyle (\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 \;.}$ 

阶数

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

指数

指数为卡邁克爾函數${\displaystyle \lambda (n)}$ ，（OEIS數列A002322），即这些循环群的阶数的最小公倍数。这意味着如果 a 和 n 互质，${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}.}$ 

生成元

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

因为所有 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$  n = 1, 2, ..., 7 是循环群，上述结论的另一种说法是：如果 n < 8 那么 ${\displaystyle \;(\mathbb {Z} /n\mathbb {Z} )^{\times }}$  有原根；如果 n ≥ 8，且不能被 4 或者两个不同的奇质数整除，${\displaystyle \;(\mathbb {Z} /n\mathbb {Z} )^{\times }}$  有原根。(  A033948 = 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 ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$  的结构和生成元。生成元不是惟一（mod n）的，比如 (mod 16) 时 {–1, 3} 和{–1, 5} 都可以。生成元以和直积因子相同的顺序列出。

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

(Z/nZ)^× 的群结构

${\displaystyle n}$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$	${\displaystyle \varphi (n)}$	${\displaystyle \lambda (n)}$	生成元		${\displaystyle n}$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$	${\displaystyle \varphi (n)}$	${\displaystyle \lambda (n)}$	生成元		${\displaystyle n}$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$	${\displaystyle \varphi (n)}$	${\displaystyle \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 elliptic curve factorization），Lenstra（英语：Arjen Lenstra） 给出的基于椭圆曲线的整数因子分解算法）

注释

1. 高斯, DA, arts. 90-91
2. 高斯, DA, arts.52-56, 82-89
3. Riesel 包含所有情形。 pp. 267-275

参考文献

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

• Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, 1986, ISBN 0387962549 

• Gauss, Carl Friedrich; Maser, H. (translator into German), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, 1965, ISBN 0-8284-0191-8 

• Riesel, Hans, Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, 1994, ISBN 0-8176-3743-5 

外部链接

• 埃里克·韦斯坦因. Modulo Multiplication Group. MathWorld.