複製鏈接
請複製以下鏈接發送給好友

整數模n乘法羣

鎖定
在同餘理論中,模 n 的互質同餘類組成一個乘法羣,稱為整數模 n 乘法羣,也稱為模 n 既約剩餘類。在環理論中,一個抽象代數的分支,也稱這個羣為整數模 n 的環的單位羣(單位是指乘法可逆元)。
這個羣是數論的基石,在密碼學整數分解素性測試均有運用。例如,關於這個羣的階(即羣的“大小”),我們可以確定如果 n質數當且僅當階數為 n-1。
中文名
整數模 n 乘法羣
別    名
模 n 既約剩餘類
學    科
數論
應    用
密碼學、整數分解和素性測試

整數模n乘法羣羣公理

容易驗證模n互質同餘類在乘法運算下滿足阿貝爾羣的公理。 [1] 
恆同: 1 是恆同;
閉:如果ab都與n互質,那麼ab也是;
逆:找x滿足ax≡ 1 (modn) 等價於解ax+ny= 1,可用歐幾里得算法求出;
結合性和交換性:由整數的相應事實以及模n運算是一個環同態推出。

整數模n乘法羣記法

整數模n環記作
(即整數環模去理想nZ= (n) ,由n的倍數組成)或
因作者所喜,它的單位羣可能記為
或類似的記號。

整數模n乘法羣結構

整數模n乘法羣2 的冪次

模 2 只有一個互質同餘類 1,所以
平凡。 [2] 
模 4 有兩個互質同餘類,1 和 3,所以
兩元循環羣。
模 8 有四個互質同餘類,1, 3, 5 和 7,每個平方都是 1,所以
Klein 四元羣。
模 16 有八個互質同餘類,1, 3, 5, 7, 9, 11, 13 和 15。
為 2-扭子羣(即每個元素的平方為 1),所以
不是循環羣。3的冪次:1,3,9,11 是一個 4 階子羣,5 的冪次也是,1,5,9,13。所以

整數模n乘法羣奇質數的冪

對奇質數的冪p,此羣是循環羣:

整數模n乘法羣一般合數

中國剩餘定理説明如果
那麼環
每個質數冪因子相應的環的直積
類似地,
的單位羣是每個質數冪因子相應羣的直積:

整數模n乘法羣階數

羣的階數由歐拉函數給出:
OEIS中的數列A000010) 這是直積中各循環階數的乘積。

整數模n乘法羣指數

指數為卡邁克爾函數,(OEIS中的數列A002322),即這些循環羣的階數的最小公倍數。這意味着如果an互質,

整數模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, ... )
一般情形每個直積因子循環有一個生成元。
參考資料
  • 1.    Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, 1986,
  • 2.    Riesel, Hans, Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, 1994