Modulo 2pⁿ 的 Primitive Root

我們已知在 modulo pⁿ 之下皆有 primitive root. 現在我們將由 modulo pⁿ 的 primitive root 找出 modulo 2pⁿ 的 primitive. 首先我們來看當 m 是奇數時 modulo m 的 order 和 modulo 2m 的 order 間之關係.

Lemma 6.3.8   給定一奇數 m, 且 a $\in$ $\mathbb {Z}$ 是一個和 m 互質的奇數. 若 ord_m(a) = n, 則 ord_2m(a) = n.

証 明. 由於 a 是奇數且與 m 互質, 故知 gcd(a, 2m) = 1. 因此 a 在 modulo 2m 之下的 order 是有定義的, 就假設 ord_2m(a) = k. 由 a^k $\equiv$ 1(mod 2m) 可得 a^k $\equiv$ 1(mod m). 故由 ord_m(a) = n 以及 Proposition 6.1.4 知 n| k. 另一方面由於 aⁿ $\equiv$ 1(mod m) 且 a 為奇數知 aⁿ $\equiv$ 1(mod 2), 故知 m| aⁿ - 1 且 2| aⁿ - 1. 又由於 m 是奇數知 gcd(2, m) = 1, 故由 Proposition 1.2.7(2) 知 2m| aⁿ - 1, 也就是說 aⁿ $\equiv$ 1(mod 2m). 因假設 ord_2m(a) = k, 故再利用 Proposition 6.1.4 得 k| n. 因此得證 k = n 也就是說 ord_2m(a) = n. $\qedsymbol$

假設 a 為 modulo pⁿ 的 primitive root, 即 ord_pⁿ(a) = $\phi$(pⁿ). 若 a 又是奇數則由 Lemma 6.3.8 知 ord_2pⁿ(a) = $\phi$(pⁿ). 但由於 p 是 奇質數與 2 互質, 故知 $\phi$(2pⁿ) = $\phi$(2)$\phi$(pⁿ) = $\phi$(pⁿ). 也就是說 ord_2pⁿ(a) = $\phi$(2pⁿ). 故由 Corollary 6.1.7 知 a 在 modulo 2pⁿ 之下亦為 primitive root. 利用此結果我們可找到 modulo 2pⁿ 的 primitive root.

Proposition 6.3.9   給定 p 是一個奇質數, 則一定可找到一奇數 a 使其在 modulo p² 之下是一個 primitive root. 特別地, 此時對任意 n $\in$ $\mathbb {N}$, a 在 modulo 2pⁿ 之下亦為 primitive root.

証 明. 當 p = 3 時, 由於 ord₃(5) = ord₃(2) = 2 故知 5 在 modulo 3 之下是一個 primitive root. 又由於 5^{3 - 1} = 25 $\not\equiv$1(mod 9), 故由 Lemma 6.3.4 知 5 在 modulo 3² 之下是一個 primitive root.

當 p$\ge$5 是一個奇質數時, Theorem 6.3.3 告訴我們在 modulo p 之下的 primitive root 存在. 現假設 $\alpha$ 是一個 modulo p 之下的 primitive root. 利用 Proposition 6.3.5 知 {$\alpha$,$\alpha$ + p,...,$\alpha$ + (p - 1)p} 中僅有一個在 modulo p² 之下不是 primitive root. 由於 p$\ge$5, 得 p - 1$\ge$4, 故知 {$\alpha$,$\alpha$ + p,$\alpha$ + 2p,$\alpha$ + 3p} 中至多有一個在 modulo p² 之下不是 primitive root. 因此若 $\alpha$ 是奇數, 則得 $\alpha$, $\alpha$ + 2p 這兩個奇數中必有一個在 modulo p² 之下是 primitive root. 若 $\alpha$ 是偶數, 則得 $\alpha$ + p, $\alpha$ + 3p 這兩個奇數中必有一個在 modulo p² 之下是 primitive root. 我們得證必存在一奇數在 modulo p² 之下是 primitive root.

現假設 a 是一奇數且在 modulo p² 之下是 primitive root. 由 Proposition 6.3.7 知 a 在 modulo pⁿ 之下亦為 primitive root. 故由 Lemma 6.3.8 知 ord_2pⁿ(a) = ord_pⁿ(a) = $\phi$(pⁿ) = $\phi$(2pⁿ), 故得證 a 在 modulo 2pⁿ 之下亦為 primitive root. $\qedsymbol$

事實上要找到一奇數使其在 modulo p² 之下是 primitive root 並不需如 Proposition 6.3.9 的證明中那麼複雜. 若 a 是偶數且在 modulo p² 之下是 primitive root, 那麼 a + p² 必為奇數且由於 a + p² $\equiv$ a(mod p²) 所以 a + p² 當然也是在 modulo p² 之下的 primitive root. 不過由於考慮 a + p² 數值較大, 我們若要找較小的 primitive root, 證明中最大只要考慮到 a + 3p, 這個數當 p 很大時當然比 a + p² 要小得多.

我們總結這兩節 Proposition 6.2.2, Proposition 6.2.4, Theorem 6.3.3, Proposition 6.3.5, Proposition 6.3.7 以及 Proposition 6.3.9 之結果得到以下所謂的 primitive root Theorem.

Theorem 6.3.10 (Primitive Root Theorem)   只有當 m = 2, 4, pⁿ, 2pⁿ 時, 其中 p 為奇質數且 n $\in$ $\mathbb {N}$, 在 modulo m 之下會有 primitive root.