Modulo p² 的 primitive root

很容易去猜測若在 modulo p² 之下有 primitive root, 那麼這個 primitive root 應來自於 modulo p 之下的 primitive root. 因此我們將利用 modulo p 的 primitive root 來找到 modulo p² 的 primitive root. 這裡的存在性的證明就比較具體, 也就是說如果能找到 modulo p 的 primitive root, 那們我們的證明能給出具體的方法來找到 modulo p² 的 primitive root.

首先我們來看如何判別一個 modulo p 的 primitive root 在 modulo p² 之下是否為 primitive root.

Lemma 6.3.4   假設 a $\in$ $\mathbb {Z}$ 是一個 primitive root modulo p. 則 ord_p²(a) = p - 1 或 ord_p²(a) = p(p - 1). 特別地, a^{p - 1} $\not\equiv$1(mod p²) 若且唯若 a 在 modulo p² 之下是一個 primitive root.

証 明. 依假設 a 在 modulo p 之下是 primitive root 表示 ord_p(a) = p - 1. 現假設 ord_p²(a) = n, 則 aⁿ $\equiv$ 1(mod p²), 因此知 aⁿ $\equiv$ 1(mod p). 故依 ord_p(a) = p - 1 及 Proposition 6.1.4 知 p - 1| n. 又因為 a 與 p 互質, 故 a 與 p² 互質, 故由 Euler's Theorem 知 a^$\phi$(p2) $\equiv$ 1(mod p²), 因此在 modulo p² 的情況再利用 Proposition 6.1.4 知 n|$\phi$(p²). 由於 $\phi$(p²) = p(p - 1), 我們得 p - 1| n 且 n| p(p - 1). 也就是 n = $\lambda$(p - 1) 且又 $\lambda$(p - 1)| p(p - 1), 故知 $\lambda$| p. 因此由 p 是質數知 $\lambda$ = 1 或 $\lambda$ = p. 故得證 ord_p²(a) = p - 1 或 ord_p²(a) = p(p - 1).

現若 a^{p - 1} $\not\equiv$1(mod p²), 知 a 在 modulo p² 之下其 order 一定不是 p - 1, 故得 ord_p²(a) = p(p - 1) = $\phi$(p²). 由 Corollary 6.1.7 得證 a 在 modulo p² 之下是一個 primitive root. 反之若 a 在 modulo p² 之下是 primitive root, 即 ord_p²(a) = p(p - 1), 故由 order 的定義知 a^{p - 1} $\not\equiv$1(mod p²). $\qedsymbol$

知道如何判別 modulo p 的 primitive root 在 modulo p² 亦是 primitive root 後, 接下來我們就要找到哪些 modulo p 的 primitive root 在 modulo p² 之下仍為 primitive root. 現假設 a 在 modulo p 之下是 primitive root, 那麼那些在 modulo p 之下和 a 同餘的數在 modulo p 之下也都是 primitive root, 但這些數在 modulo p² 之下可能不同餘, 我們就將它們一一列出. 也就是說, a, a + p,..., a + (p - 1)p, 共有這 p 個數是在 modulo p 之下同餘但在 modulo p² 之下不同餘.

Proposition 6.3.5   假設 p 是一個質數且 a $\in$ $\mathbb {Z}$ 為一個在 modulo p 之下的 primitive root. 令 S = {a, a + p, a + 2p + ^... , a + (p - 1)p}, 則在 S 中僅有一個元素在 modulo p 之下不是 primitive root, 其餘 p - 1 個元素在 modulo p 之下是 primitive root.

証 明. 已知 a 在 modulo p 之下是 primitive root 且 S 中的元素在 modulo p 之下皆與 a 同餘, 故知 S 中的元素在 modulo p 之下皆為 primitive root. 所以我們可以利用 Lemma 6.3.4 檢查 S 中哪些元素 a + tp 會使得 (a + tp)^{p - 1} $\equiv$ 1(mod p²).

由於 a^{p - 1} $\equiv$ 1(mod p), 故存在 $\lambda$ $\in$ $\mathbb {Z}$ 使得 a^{p - 1} = 1 + $\lambda$p. 因此

(a + tp)^{p - 1} = a^{p - 1} + (p - 1)a^{p - 2}(tp) + $${\frac{(p-1)(p-2)}{2}}$$a^{p - 3}(tp)² + ^...

由於 C₂^{p - 1}a^{p - 3}(tp)² 這一項以及其之後每一項 C^{p - 1}_ka^{p - 1 - k}(tp)^k, k$\ge$3 在 modulo p² 之下皆為 0, 所以我們得

(a + tp)^{p - 1} $$\equiv$$ a^{p - 1} - a^{p - 2}tp $$\equiv$$ 1 + ($$\lambda$$ - a^{p - 2}t)p(mod p²).

因此要找到 t 使得 (a + tp)^{p - 1} $\equiv$ 1(mod p²) 若且唯若 p|$\lambda$ - a^{p - 2}t. 也就是說我們要找到 t $\in$ {0, 1, 2,..., p - 1} 使得 a^{p - 2}t $\equiv$ $\lambda$(mod p). 然而 a^{p - 1} $\equiv$ 1(mod p), 故上式兩邊乘上 a 得 t $\equiv$ a$\lambda$(mod p). 也就是說當 0$\le$t$\le$p - 1, 僅有 t $\equiv$ a$\lambda$(mod p) 時, 會使得 (a + tp)^{p - 1} $\equiv$ 1(mod p²), 此時 a + tp 在 modulo p² 之下不是 primitive root. 其餘 S 中的元素 a + rp 由於皆會使得 (a + rp)^{p - 1} $\not\equiv$1(mod p²), 故由 Lemma 6.3.4 知皆為 modulo p² 之下的 primitive root. $\qedsymbol$

從 Theorem 6.3.3 以及 Proposition 6.3.5 我們知道由於 modulo p 的 primitive root 存在, 所以 modulo p² 的 primitive root 也存在. 事實上若 a 是 modulo p 的 primitive root, 我們僅要檢驗是否 a^{p - 1} $\equiv$ 1(mod p²). 要是 a^{p - 1} $\not\equiv$1(mod p²), 那麼由 Lemma 6.3.4, 我們知 a 在 modulo p² 之下是 primitive root. 要是 a^{p - 1} $\equiv$ 1(mod p²), 那麼 a 在 modulo p² 之下不是 primitive root, 故由 Proposition 6.3.5 知 a + p 在 modulo p² 之下必為 primitive root.