Modulo p 的 Primitive Root

我們要說明當 p 是一個奇質數時在 modulo p 之下可以找到 primitive root. 我們曾經提及要證明存在性, 一般來說有兩種方法: 第一種就是提供一個可以找到東西的方法; 另一種就是利用邏輯推演的方式來推導出東西一定存在 (例如用反證法證明若找不到會導致矛盾). 第一種方法的好處是它提供了找到東西的方法所以不只告訴你東西存在且告訴你如何找到. 不過這在一般抽象理論的推導中不是容易的, 例如前一章提過找二次 congruence equation 的解並不容易, 但我們可發展一套理論來確認何時有解. 同樣地, 在證明 primitive root 存在的問題上, 即使已知存在到目前為止仍沒有一套完善的方法可以直接找到 primitive root, 所以我們仍是用邏輯推演的方式來證明存在性.

在 modulo p 時, 有一件事是很特殊的即 Theorem 4.1.3 告訴我們一個 n 次的整係數多項式在 modulo p 之下最多有 n 個解. 然而若 p$\nmid$a 且 ord_p(a) = n, 已知 a, a²,..., aⁿ 在 modulo p 之下皆相異, 且由於 aⁿ $\equiv$ 1(mod p), 故 (aⁱ)ⁿ $\equiv$ 1(mod p). 由此可知 a, a²,..., aⁿ 這 n 個在 modulo p 之下皆不同餘的數皆為 xⁿ $\equiv$ 1(mod p) 的一個解, 但由於此式在 modulo p 之下至多有 n 個解, 所以它們就是 xⁿ $\equiv$ 1(mod p) 所有的解. 另一方面, 若 p$\nmid$b 且 ord_p(b) = n, 則由於 b 是 xⁿ $\equiv$ 1(mod p) 之一解, 故由前知存在 i $\in$ {1,..., n} 使得 b $\equiv$ aⁱ(mod p). 換言之, 所有在 modulo p 之下 order 為 n 的元素, 在 modulo p 之下必和 {a, a²,..., aⁿ} 中某個元素同餘, 故利用 Corollary 6.1.9 知在 modulo p 之下僅有 $\phi$(n) 個元素其 order 為 n. 我們將此結果總結如下.

Lemma 6.3.1   假設 p 為質數且在 modulo p 之下有一元素其 order 為 n, 則在 modulo p 之下共有 $\phi$(n) 個元素其 order 為 n.

再次強調, 此結果在質數時才對. 例如在 modulo 15 時, 共有 4, 11 和 14 三個元素在 modulo 15 之下的 order 為 2, 而不是 $\phi$(2) = 1 個.

我們要說在 modulo p 之下有 primitive root 主要的方法便是將 modulo p 之下的元素依其 order 分類. 最後說明 order 為 $\phi$(p) = p - 1 那一類元素所成的集合不是 $\emptyset$ (空集合). 下面就是依這樣分類所得之結果.

Lemma 6.3.2   假設 p 是質數且令 S = {1, 2,..., p - 1}. 現對於 d $\in$ $\mathbb {N}$ 滿足 d| p - 1, 我們考慮 S_d = {i $\in$ S | ord_p(i) = d}.

1. 若 d$\ne$d', 則 S_d $\cap$ S_d' = $\emptyset$.
2. $\bigcup\limits_{d\vert p-1,d>0}^{}$S_d = S.
3. 若 S_d$\ne$$\emptyset$, 則 S_d 共有 $\phi$(d ) 個元素.

証 明. (1) 若 a $\in$ S_d $\cap$ S_d', 即表示 ord_p(a) = d 且 ord_p(a) = d'. 但依 order 的定義每一個和 p 互質的數在 modulo p 之下其 order 是唯一的, 此與 d$\ne$d' 之假設相矛盾, 故知 S_d $\cap$ S_d' = $\emptyset$.

(2) $\bigcup\limits_{d\vert p-1,d>0}^{}$S_d 這個符號的意思是將所有 S_d 其中 d $\in$ $\mathbb {N}$ 且 d| p - 1 聯集起來. 由於對所有 d| p - 1 皆有 S_d $\subseteq$ S, 所以 $\bigcup\limits_{d\vert p-1,d>0}^{}$S_d $\subseteq$ S. 另一方面若 i $\in$ S, 由於 p$\nmid$i, 故由 Theorem 3.3.4 知 i^{p - 1} $\equiv$ 1(mod p). 因此由 Proposition 6.1.4 知 ord_p(i)| p - 1. 換句話說, 若 ord_p(i) = d, 則 d| p - 1, 故知存在 d| p - 1 使得 i $\in$ S_d. 得證 S $\subseteq$ $\bigcup\limits_{d\vert p-1,d>0}^{}$S_d, 因此知 $\bigcup\limits_{d\vert p-1,d>0}^{}$S_d = S.

(3) 若 S_d$\ne$$\emptyset$, 表示存在 a $\in$ S_d. 此時 p$\nmid$a 且 ord_p(a) = d, 故利用 Lemma 6.3.1 知在 modulo p 之下共有 $\phi$(d ) 個元素其 order 為 d. 由於 S 是 reduced residue system modulo p, 這 $\phi$(d ) 個元素在 modulo p 之下必和 S 中 $\phi$(d ) 個元素同餘. 因此 S 中這 $\phi$(d ) 個元素剛好組成 S_d, 故知 S_d 共有 $\phi$(d ) 個元素. $\qedsymbol$

Lemma 6.3.2(1,2) 告訴我們 S = {1, 2,..., p - 1} 中的每一個元素必會落在某個且恰有一個 S_d 中, 其中 d $\in$ $\mathbb {N}$ 且 d| p - 1. 因此若計算每個 S_d 中的元素個數再加總起來其值應為 S 中的元素個數 p - 1. 依此我們可以得到以下重要的結果.

Theorem 6.3.3   假設 p 是一個質數且 d $\in$ $\mathbb {N}$ 滿足 d| p - 1. 則在 modulo p 之下共有 $\phi$(d ) 個元素其 order 為 d. 特別地, 在 modulo p 之下 primitive root 必存在.

証 明. 我們沿用 Lemma 6.3.2 中所用的符號, 並令 n(d ) 表示 S_d = {i $\in$ S | ord_p(i) = d} 中元素的個數, 即 n(d ) 為在 modulo p 之下 order 為 d 的元素個數.

由 Lemma 6.3.2(1,2) 我們知 $\sum\limits_{d\vert p-1,d>0}^{}$n(d )= p - 1 而且 Lemma 6.3.2(3) 告訴我們 n(d )= 0 或 n(d )= $\phi$(d ). 另一方面利用 Corollary 2.3.6 我們知 $\sum\limits_{d\vert p-1,d>0}^{}$$\phi$(d )= p - 1, 而 $\phi$(d ) > 0, 故比較 $\sum\limits_{d\vert p-1,d>0}^{}$n(d )= $\sum\limits_{d\vert p-1,d>0}^{}$$\phi$(d ), 可得對所有的 d $\in$ $\mathbb {N}$ 滿足 d| p - 1 皆有 n(d )= $\phi$(d ).

特別地 n(p - 1) = $\phi$(p - 1) 表示在 modulo p 之下有 $\phi$(p - 1)$\ne$ 0 個元素其 order 為 p - 1, 也就是說這些元素皆為 primitive root. 故知在 modulo p 之下 primitive root 是存在的. $\qedsymbol$

我們證明了在 modulo p 之下 primitive root 是存在的. 這個證明方式很明顯的並沒有告訴我們如何找到 primitive root. 事實上我們所用的證明方式有點像反證法, 也就是說如果沒有 primitive root, 那麼在計算上面那些元素個數時會發生數目兜不攏的情形而造成矛盾.