# 整数模n乘法群

## 结构

### 一般合数

${\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 }\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 }}$循环群当且仅当 ${\displaystyle \varphi (n)=\lambda (n).}$ 这在 n 为奇质数的幂次、奇质数幂次 2 倍、2 和 4 成立，此时也称一个生成元为模 n 的原根

## 列表

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 }}$ 中元素都是 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 意味着任何 ${\displaystyle \mathbb {Z} _{20}^{\times }}$ 中数的 4 次幂 ≡ 1 (mod 20)。

${\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 }}$ C1 1 1 0 C2×C8 16 8 31, 3 C6×C6 36 6 2, 5 C1 1 1 1 C2×C10 20 10 10, 2 C2×C16 32 16 3, 63 C2 2 2 2 C16 16 16 3 C4×C12 48 12 2, 12 C2 2 2 3 C2×C12 24 12 6, 2 C2×C10 20 10 5, 7 C4 4 4 2 C2×C6 12 6 19, 5 C66 66 66 2 C2 2 2 5 C36 36 36 2 C2×C16 32 16 3, 67 C6 6 6 3 C18 18 18 3 C2×C22 44 22 2, 68 C2×C2 4 2 7, 3 C2×C12 24 12 38, 2 C2×C12 24 12 3, 11 C6 6 6 2 C2×C2×C4 16 4 39, 11, 3 C70 70 70 7 C4 4 4 3 C40 40 40 6 C2×C2×C6 24 12 5, 7, 11 C10 10 10 2 C2×C6 12 6 13, 5 C72 72 72 5 C2×C2 4 2 5, 7 C42 42 42 3 C36 36 36 5 C12 12 12 2 C2×C10 20 10 43, 3 C2×C20 40 20 2, 74 C6 6 6 3 C2×C12 24 12 44, 2 C2×C18 36 18 3, 75 C2×C4 8 4 14, 2 C22 22 22 5 C2×C30 60 30 2, 76 C2×C4 8 4 15, 3 C46 46 46 5 C2×C12 24 12 5, 7 C16 16 16 3 C2×C2×C4 16 4 47, 7, 5 C78 78 78 3 C6 6 6 5 C42 42 42 3 C2×C4×C4 32 4 3, 7, 11 C18 18 18 2 C20 20 20 3 C54 54 54 2 C2×C4 8 4 19, 3 C2×C16 32 16 50, 5 C40 40 40 7 C2×C6 12 6 20, 2 C2×C12 24 12 51, 7 C82 82 82 2 C10 10 10 7 C52 52 52 2 C2×C2×C6 24 12 5, 11, 13 C22 22 22 5 C18 18 18 5 C4×C16 64 16 2, 3 C2×C2×C2 8 2 5, 7, 13 C2×C20 40 20 21, 2 C42 42 42 3 C20 20 20 2 C2×C2×C6 24 6 13, 29, 3 C2×C28 56 28 2, 86 C12 12 12 7 C2×C18 36 18 20, 2 C2×C2×C10 40 10 3, 5, 7 C18 18 18 2 C28 28 28 3 C88 88 88 3 C2×C6 12 6 13, 3 C58 58 58 2 C2×C12 24 12 7, 11 C28 28 28 2 C2×C2×C4 16 4 11, 19, 7 C6×C12 72 12 2, 3 C2×C4 8 4 11, 7 C60 60 60 2 C2×C22 44 22 3, 91 C30 30 30 3 C30 30 30 3 C2×C30 60 30 5, 11

## 参见

Lenstra 椭圆曲线分解en:Lenstra elliptic curve factorizationLenstra 给出的基于椭圆曲线的整数因子分解算法）

## 注释

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

## 参考文献

• 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