整数模n乘法群
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在同余理论中,模 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 环记作 或 (即整数环模去理想 nZ = (n) ,由 n 的倍数组成)或 因作者所喜,它的单位群可能记为 或类似的记号,本文采用
结构
[编辑]2 的幂次
[编辑]模 2 只有一个互质同余类 1,所以 平凡。
模 4 有两个互质同余类,1 和 3,所以 两元循环群。
模 8 有四个互质同余类,1, 3, 5 和 7,每个平方都是 1,所以 Klein 四元群。
模 16 有八个互质同余类,1, 3, 5, 7, 9, 11, 13 和 15。 为 2-扭子群(即每个元素的平方为 1),所以 不是循环群。3的幂次: 是一个 4 阶子群,5 的幂次也是,。所以 。
以上 8 和 16 的讨论对高阶幂次 2k, k > 2[1] 也成立: 是 2-扭子群(所以 不是循环)而 3 的幂次是一个2k- 2 子群,所以 。
奇素数的幂
[编辑]对奇素数的幂 pk,此群是循环群:[2]
一般合数
[编辑]中国剩余定理[3] 说明如果 那么环 每个素数幂因子相应的环的直积:
类似地, 的单位群是每个素数幂因子相应群的直积:
阶数
[编辑]群的阶数由欧拉函数给出: (OEIS数列A000010) 这是直积中各循环阶数的乘积。
指数
[编辑]指数为卡迈克尔函数,(OEIS数列A002322),即这些循环群的阶数的最小公倍数。这意味着如果 a 和 n 互质,
生成元
[编辑]是循环群当且仅当 这在 n 为奇素数的幂次、奇素数幂次 2 倍、2 和 4 成立,此时也称一个生成元为模 n 的原根。
因为所有 n = 1, 2, ..., 7 是循环群,上述结论的另一种说法是:如果 n < 8 那么 有原根;如果 n ≥ 8,且不能被 4 或者两个不同的奇素数整除, 有原根。( 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 的结构和生成元。生成元不是惟一(mod n)的,比如 (mod 16) 时 {–1, 3} 和{–1, 5} 都可以。生成元以和直积因子相同的顺序列出。
以 n=20 为例。 意味着 的阶数是 8(即有 8 个小于 20 的正整数与其互质); 说明任何和20互质的数的 4 次幂≡ 1(mod 20);至于生成元,19 的指数为2,3 的指数为 4,而任何 中元素都是 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 意味着任何 中数的 4 次幂 ≡ 1 (mod 20)。
生成元 | 生成元 | 生成元 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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)由西塞罗拉丁语翻译成英语和德语。德语版包含他所有数论的论文:所有关于二次互反律的证明,高斯和符号的确定,双二次互反律的研究以及未发表的笔记。
- 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