整數模n乘法群

同餘理論中,模 n互質同餘類組成一個乘法,稱為整數模 n 乘法群,也稱為模 n 最簡剩餘類。在環理論中,一個抽象代數的分支,也稱這個群為整數模 n 的環的單位群(單位是指乘法可逆元素)。

群論


這個群是數論的基石,在密碼學整數分解質數測試均有運用。例如,關於這個群的階(即群的「大小」),我們可以確定如果 n質數當且僅當階數為 n-1。

群公理

編輯

容易驗證模 n 互質同餘類在乘法運算下滿足阿貝爾群的公理。

互質同餘類的乘法是良好定義:an 互質,當且僅當 gcd(a, n) = 1. 同餘類中的整數ab (mod n) 滿足gcd(a, n) = gcd(b, n), 因此一個整數與 n 互質當且僅當另一個整數也與 n 互質.
恆同: 1 是恆同; 1所在的同餘類是唯一的乘法恆同類
閉:如果 ab 都與 n 互質,那麼 ab 也是;因為gcd(a, n) = 1gcd(b, n) = 1 意味着 gcd(ab, n) = 1, 與 n 互質的同餘類在乘法下是封閉的。
逆:找 x 滿足 ax ≡ 1 (mod n) 等價於解 ax + ny = 1,可用歐幾里得算法求出x,並且x在模n的同餘類里。當 an 互質, 由於 gcd(a, n) = 1 ,根據 貝祖定理 存在整數 xy 滿足 ax + ny = 1. 注意到由等式 ax + ny = 1 可推出 xn 互質, 所以乘法反元素屬於群.
結合性和交換性:由整數的相應事實以及模 n 運算是一個環同態推出。由於同餘類aa' bb' (mod n) 的整數乘法意味着 aba'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),即這些循環群的階數的最小公倍數。這意味着如果 an 互質, 

生成元

編輯

 循環群當且僅當   這在 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)。

(Z/nZ)× 的群結構
        生成元           生成元           生成元
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

參見

編輯

註釋

編輯
  1. ^ 高斯, DA, arts. 90-91
  2. ^ 高斯, DA, arts.52-56, 82-89
  3. ^ 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 

外部連結

編輯