整数模n乘法群

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

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

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

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

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

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

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

结合性和交换性：由整数的相应事实以及模 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高斯, DA, arts. 90-91 也成立：
 是 2-扭子群（所以  不是循环）而 3 的幂次是一个2k- 2 子群，所以 。

 奇质数的幂 
对奇质数的幂 pk，此群是循环群：高斯, DA, arts.52-56, 82-89 

一般合数
中国剩余定理Riesel 包含所有情形。 pp. 267-275 说明如果 那么环  每个质数幂因子相应的环的直积：



类似地， 的单位群是每个质数幂因子相应群的直积：

 阶数 
群的阶数由欧拉函数给出： 
这是直积中各循环阶数的乘积。

 指数 
指数为卡邁克爾函數，，即这些循环群的阶数的最小公倍数。这意味着如果 a 和 n 互质，

 生成元 
 是循环群当且仅当  这在 n 为奇质数的幂次、奇质数幂次 2 倍、2 和 4 成立，此时也称一个生成元为模 n 的原根。

因为所有  n = 1, 2, ..., 7 是循环群，上述结论的另一种说法是：如果 n < 8 那么  有原根；如果 n ≥ 8，且不能被 4 或者两个不同的奇质数整除， 有原根。( = 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)。

+ (Z/nZ)× 的群结构         生成元           生成元           生成元 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

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

 注释 

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






 外部链接 


Category:同余
Category:群论
Category:有限群