整數模n乘法群

在同餘理論中，模 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 環記作 $\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 < 8 那麼 $\;(\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)。

$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\lambda(n)$｜生成元｜$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\lambda(n)$｜生成元｜$n$｜$(\mathbb{Z}/n\mathbb{Z})^\times$｜$\varphi(n)$｜$\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給出的基於橢圓曲線的整數因子分解演算法。

## 參考文獻

高斯的算術研究（Disquisitiones Arithemeticae）由古典拉丁語翻譯成英語和德語。德語版包含他所有數論的論文：所有關於二次互反律的證明，高斯和符號的確定，雙二次互反律的研究以及未發表的筆記。