整数模n乘法群

2024-07-04 07:47| 来源: 网络整理| 查看: 265

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

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

目录 1 群公理 2 记法 3 结构 3.1 2 的幂次 3.2 奇质数的幂 3.3 一般合数 4 阶数 5 指数 6 生成元 7 列表 8 参见 9 注释 10 参考文献 11 外部链接群公理

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

结构 2 的幂次

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

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

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

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

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

奇质数的幂

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

一般合数

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

Z / n Z ≅ Z / p 1 k 1 Z × Z / p 2 k 2 Z × Z / p 3 k 3 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 \;\;}

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

( Z / n Z ) × ≅ ( Z / p 1 k 1 Z ) × × ( Z / p 2 k 2 Z ) × × ( Z / p 3 k 3 Z ) × … . {\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 \;.} 阶数

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

指数

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

生成元

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

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

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

(Z/nZ)× 的群结构 n {\displaystyle n} ( Z / n Z ) × {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }} φ ( n ) {\displaystyle \varphi (n)} λ ( n ) {\displaystyle \lambda (n)} 生成元 n {\displaystyle n} ( Z / n Z ) × {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }} φ ( n ) {\displaystyle \varphi (n)} λ ( n ) {\displaystyle \lambda (n)} 生成元 n {\displaystyle n} ( Z / n Z ) × {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }} φ ( n ) {\displaystyle \varphi (n)} λ ( 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）给出的基于椭圆曲线的整数因子分解算法）

注释 ^ 高斯, DA, arts. 90-91 ^ 高斯, DA, arts.52-56, 82-89 ^ 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.

【本文地址】

整数模n乘法群

整数模n乘法群

今日新闻

推荐新闻