整數模n乘法群
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在同餘理論中,模 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 環記作 或 (即整數環模去理想 nZ = (n) ,由 n 的倍數組成)或 因作者所喜,它的單位群可能記為 或類似的記號,本文採用
結構
2 的冪次
模 2 只有一個互質同餘類 1,所以 平凡。
模 4 有兩個互質同餘類,1 和 3,所以 兩元循環群。
模 8 有四個互質同餘類,1, 3, 5 和 7,每個平方都是 1,所以 Klein 四元群。
模 16 有八個互質同餘類,1, 3, 5, 7, 9, 11, 13 和 15。 為 2-扭子群(即每個元素的平方為 1),所以 不是循環群。3的冪次: 是一個 4 階子群,5 的冪次也是,。所以 。
以上 8 和 16 的討論對高階冪次 2k, k > 2[1] 也成立: 是 2-扭子群(所以 不是循環)而 3 的冪次是一個2k- 2 子群,所以 。
奇質數的冪
對奇質數的冪 pk,此群是循環群:[2]
一般合數
中國剩餘定理[3] 說明如果 那麼環 每個質數冪因子相應的環的直積:
類似地, 的單位群是每個質數冪因子相應群的直積:
階數
群的階數由歐拉函數給出: (OEIS數列A000010) 這是直積中各循環階數的乘積。
指數
指數為卡邁克爾函數,(OEIS數列A002322),即這些循環群的階數的最小公倍數。這意味着如果 a 和 n 互質,
生成元
是循環群當且僅當 這在 n 為奇質數的冪次、奇質數冪次 2 倍、2 和 4 成立,此時也稱一個生成元為模 n 的原根。
因為所有 n = 1, 2, ..., 7 是循環群,上述結論的另一種說法是:如果 n < 8 那麼 有原根;如果 n ≥ 8,且不能被 4 或者兩個不同的奇質數整除, 有原根。( 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 的結構和生成元。生成元不是惟一(mod n)的,比如 (mod 16) 時 {–1, 3} 和{–1, 5} 都可以。生成元以和直積因子相同的順序列出。
以 n=20 為例。 意味着 的階數是 8(即有 8 個小於 20 的正整數與其互質); 說明任何和20互質的數的 4 次冪≡ 1(mod 20);至於生成元,19 的指數為2,3 的指數為 4,而任何 中元素都是 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 意味着任何 中數的 4 次冪 ≡ 1 (mod 20)。
生成元 | 生成元 | 生成元 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
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)由西塞羅拉丁語翻譯成英語和德語。德語版包含他所有數論的論文:所有關於二次互反律的證明,高斯和符號的確定,雙二次互反律的研究以及未發表的筆記。
- 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