既约剩余类

在同餘理論中，模 _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)$ （即整數環模去理想 _n_**Z** = (_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}}$ 。

### 奇質數的冪

對奇質數的冪 _p_k，此群是循環群： $\;\;(\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).$ （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 }$ 中元素都是 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)。
> 
> 

## 參見

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

## 外部連結

* 埃里克・韋斯坦因. Modulo Multiplication Group. MathWorld.