整數模n乘法群

群論
	;
	群
基本概念
	子群 · 正規子群 · 商群 · 群同態 · 像 · (半)直積 · 直和; 單純群 · 有限群 · 無限群 · 拓撲群 · 群概形 · 循環群 · 冪零群 · 可解群 · 圈積
離散群
	有限單群分類 ; 循環群 Zn ; 交錯群 An ; 李型群; 散在群; 馬蒂厄群 M11..12,M22..24; 康威群 Co1..3 ; 揚科群 J1..4 ; 費歇爾群（英語：Fischer group）F22..24; 子魔群（英語：sub monster group） B; 魔群 M; 其他有限群; 對稱群, Sn; 二面體群, Dn; 無限群; 整數, Z; 模群, PSL(2,Z) 和 SL(2,Z);
連續群
	李群; 一般線性群 GL(n); 特殊線性群 SL(n); 正交群 O(n); 特殊正交群 SO(n); 么正群 U(n); 特殊么正群 SU(n); 辛群 Sp(n); G2 F4 E6 E7 E8; 勞侖茲群; 龐加萊群;
無限維群
	共形群; 微分同胚群 ; 環路群 ; 量子群 ; O(∞) SU(∞) Sp(∞);
代數群
	橢圓曲線; 線性代數群（英語：Linear algebraic group）; 阿貝爾簇（英語：Abelian variety）
	閱; 論; 編;

在同餘理論中，模 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 的討論對高階冪次 2^k, k > 2^[1] 也成立： $\{\pm 1,2^{k-1}\pm 1\}\cong C_{2}\times C_{2},$ 是 2-扭子群（所以 $(\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }$ 不是循環）而 3 的冪次是一個2^{k- 2} 子群，所以 $(\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong C_{2}\times C_{2^{k-2}}$ 。

奇質數的冪

對奇質數的冪 p^k，此群是循環群：^[2] $\;\;(\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}}\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).$ （OEIS數列A000010）這是直積中各循環階數的乘積。

指數

指數為卡邁克爾函數 $\lambda (n)$ ，（OEIS數列A002322），即這些循環群的階數的最小公倍數。這意味著如果 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 }$ 有原根。( 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 $(\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 }$ 中元素都是 19^a × 3^b 的形式，這裡 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)。

**(Z/nZ)^×** 的群結構
$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	C₁	1	1	0	32	C₂×C₈	16	8	31, 3	63	C₆×C₆	36	6	2, 5
2	C₁	1	1	1	33	C₂×C₁₀	20	10	10, 2	64	C₂×C₁₆	32	16	3, 63
3	C₂	2	2	2	34	C₁₆	16	16	3	65	C₄×C₁₂	48	12	2, 12
4	C₂	2	2	3	35	C₂×C₁₂	24	12	6, 2	66	C₂×C₁₀	20	10	5, 7
5	C₄	4	4	2	36	C₂×C₆	12	6	19, 5	67	C₆₆	66	66	2
6	C₂	2	2	5	37	C₃₆	36	36	2	68	C₂×C₁₆	32	16	3, 67
7	C₆	6	6	3	38	C₁₈	18	18	3	69	C₂×C₂₂	44	22	2, 68
8	C₂×C₂	4	2	7, 3	39	C₂×C₁₂	24	12	38, 2	70	C₂×C₁₂	24	12	3, 11
9	C₆	6	6	2	40	C₂×C₂×C₄	16	4	39, 11, 3	71	C₇₀	70	70	7
10	C₄	4	4	3	41	C₄₀	40	40	6	72	C₂×C₂×C₆	24	12	5, 7, 11
11	C₁₀	10	10	2	42	C₂×C₆	12	6	13, 5	73	C₇₂	72	72	5
12	C₂×C₂	4	2	5, 7	43	C₄₂	42	42	3	74	C₃₆	36	36	5
13	C₁₂	12	12	2	44	C₂×C₁₀	20	10	43, 3	75	C₂×C₂₀	40	20	2, 74
14	C₆	6	6	3	45	C₂×C₁₂	24	12	44, 2	76	C₂×C₁₈	36	18	3, 75
15	C₂×C₄	8	4	14, 2	46	C₂₂	22	22	5	77	C₂×C₃₀	60	30	2, 76
16	C₂×C₄	8	4	15, 3	47	C₄₆	46	46	5	78	C₂×C₁₂	24	12	5, 7
17	C₁₆	16	16	3	48	C₂×C₂×C₄	16	4	47, 7, 5	79	C₇₈	78	78	3
18	C₆	6	6	5	49	C₄₂	42	42	3	80	C₂×C₄×C₄	32	4	3, 7, 11
19	C₁₈	18	18	2	50	C₂₀	20	20	3	81	C₅₄	54	54	2
20	C₂×C₄	8	4	19, 3	51	C₂×C₁₆	32	16	50, 5	82	C₄₀	40	40	7
21	C₂×C₆	12	6	20, 2	52	C₂×C₁₂	24	12	51, 7	83	C₈₂	82	82	2
22	C₁₀	10	10	7	53	C₅₂	52	52	2	84	C₂×C₂×C₆	24	12	5, 11, 13
23	C₂₂	22	22	5	54	C₁₈	18	18	5	85	C₄×C₁₆	64	16	2, 3
24	C₂×C₂×C₂	8	2	5, 7, 13	55	C₂×C₂₀	40	20	21, 2	86	C₄₂	42	42	3
25	C₂₀	20	20	2	56	C₂×C₂×C₆	24	6	13, 29, 3	87	C₂×C₂₈	56	28	2, 86
26	C₁₂	12	12	7	57	C₂×C₁₈	36	18	20, 2	88	C₂×C₂×C₁₀	40	10	3, 5, 7
27	C₁₈	18	18	2	58	C₂₈	28	28	3	89	C₈₈	88	88	3
28	C₂×C₆	12	6	13, 3	59	C₅₈	58	58	2	90	C₂×C₁₂	24	12	7, 11
29	C₂₈	28	28	2	60	C₂×C₂×C₄	16	4	11, 19, 7	91	C₆×C₁₂	72	12	2, 3
30	C₂×C₄	8	4	11, 7	61	C₆₀	60	60	2	92	C₂×C₂₂	44	22	3, 91
31	C₃₀	30	30	3	62	C₃₀	30	30	3	93	C₂×C₃₀	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.

[1] 高斯, DA, arts. 90-91

[2] 高斯, DA, arts.52-56, 82-89

[3] Riesel 包含所有情形。 pp. 267-275

[1]

[2]

[3]