在同余理论中，模 n 的互质同余类组成一个乘法群，称为整数模 n 乘法群，也称为模 n 既约剩余类。在环理论中，一个抽象代数的分支，也称这个群为整数模 n 的环的单位群（单位是指乘法可逆元）。
这个群是数论的基石，在密码学、整数分解和 質數測試}-均有运用。例如，关于这个群的阶（即群的“大小”），我们可以确定如果 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 环记作 \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 \;(\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)。
参见
- ，给出的基于椭圆曲线的整数因子分解算法。
注释
参考文献
高斯的算术研究（Disquisitiones Arithemeticae）由古典拉丁語翻译成英语和德语。德语版包含他所有数论的论文：所有关于二次互反律的证明，高斯和符号的确定，双二次互反律的研究以及未发表的笔记。
*
*
*
外部链接
*
评论 (0)