沒有 Primitive Root 的情況

我們將探討有哪些 m 在 modulo m 之下沒有 primitive root.

我們仍然從唯一的偶質數 2 出發. 在 modulo 2 之下 $\phi$(2) = 1, 而任何的奇數在 modulo 2 之下皆餘 1, 故所有的奇數皆為 primitive root. 在 modulo 4 時, {1, 3} 是一個 reduced residue system modulo 4, 而 3¹ $\not\equiv$1(mod 4) 且 3² $\equiv$ 1(mod 4) 故得 ord₄(3) = 2 = $\phi$(4), 故知 3 在 modulo 4 之下是 primitive root. 事實上若 a $\in$ $\mathbb {Z}$ 滿足 a $\equiv$ 3(mod 4) 則 a 在 modulo 4 之下為 primitive root.

接著我們來看 8 情形, 由於 {1, 3, 5, 7} 是一個 reduced residue system modulo 8, 我們來看看它們在 modulo 8 之下之 order 為何. 很明顯的 ord₈(1) = 1 且因為 7 $\equiv$ - 1(mod 8), 故知 ord₈(7) = 2. 另外 3¹ $\equiv$ 3(mod 8) 且 3² $\equiv$ 1(mod 8), 故知 ord₈(3) = 2. 同理得 ord₈(5) = 2. 由於所有和 8 互質的數在 modulo 8 之下必和 1, 3, 5, 7 中某一數同餘, 因此由 Lemma 6.1.3(1) 知沒有一個和 8 互質的數其在 modulo 8 之下的 order 為 $\phi$(8) = 4. 故知在 modulo 8 之下沒有 primitive root.

或許大家看到 modulo 8 之下沒有 primitive root 很自然會認為那麼在 modulo 16 之下也沒有 primitive root. 事實上這件事並不能直接用 order 的定義得到. 也就是說若已知 ord₈(a) = n 並不能直接用 order 的性質推出 ord₁₆(a) 之值. 頂多我們知道若 ord₁₆(a) = n', 則由 a^n' $\equiv$ 1(mod 16) 可知 a^n' $\equiv$ 1(mod 8), 故利用 Proposition 6.1.4 得 n| n'. 但我們並不能由此以及 n < $\phi$(8) 推出 n' < $\phi$(16). 所以要推出在 modulo 16 或甚至 modulo 2ⁿ, n > 3 時沒有 primitive root, 是需要多下功夫的. 在前面我們已算出對任意奇數 a, 皆滿足 a² $\equiv$ 1(mod 2³). 我們要用歸納法推出以下結果.

Lemma 6.2.1   假設 a 為一奇數, 則對任意 n $\in$ $\mathbb {N}$ 皆有 a²ⁿ $\equiv$ 1(mod 2^{n + 2}).

証 明. 我們已知當 n = 1 時這是對的. 假設當 n = k 時皆有 a^2k $\equiv$ 1(mod 2^{k + 2}), 我們要證明當 n = k + 1 時亦成立. 依假設我們知存在 b $\in$ $\mathbb {Z}$ 使得 a^2k = 1 + 2^{k + 2}b. 故

a^{2k + 1} = (a^2k)² = (1 + 2^{k + 2}b)² = 1 + 2(2^{k + 2}b) + (2^{k + 2}b)².

由於 2(k + 2) = k + (k + 4) > k + 3, 我們得 a^{2k + 1} $\equiv$ 1(mod 2^{k + 3}). 也就是說當 n = k + 1 時 a²ⁿ $\equiv$ 1(mod 2^{n + 2}) 亦成立, 故由數學歸納法得證本定理. $\qedsymbol$

依 order 的定義我們馬上由 Lemma 6.2.1 知當 a 為奇數且 n $\in$ $\mathbb {N}$ 時,

ord_{2^{n + 2}}(a)$$\le$$2ⁿ < 2^{n + 1} = $$\phi$$(2^{n + 2}),

故得證以下重要的結果.

Proposition 6.2.2   當 n $\in$ $\mathbb {N}$ 且 n$\ge$3 時, 在 modulo 2ⁿ 之下沒有 primitive root.

接下來我們要探討另一種沒有 primitive root 的情況, 首先我們來看另一個有關 order 簡單的性質.

Lemma 6.2.3   給定互質的兩正整數 m, n 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, mn) = 1. 則

ord_mn(a)$$\le$$$${\frac{\phi(mn)}{\gcd(\phi(m),\phi(n))}}$$.

証 明. 令 d = gcd($\phi$(m),$\phi$(n)). 由於 gcd(a, mn) = 1, 我們知 gcd(a, m) = gcd(a, n) = 1. 因此由 Euler's Theorem 我們有 a^$\phi$(m) $\equiv$ 1(mod m) 以及 a^$\phi$(n) $\equiv$ 1(mod n). 因此由 $\phi$(mn) = $\phi$(m)$\phi$(n) (因 gcd(m, n) = 1) 以及 $\phi$(n)/d $\in$ $\mathbb {N}$ 可得

a^{${\frac{\phi(mn)}{d}}$} = (a^$\phi$(m))^{${\frac{\phi(n)}{d}}$} $$\equiv$$ 1(mod m).

同理可得 a^$\phi$(mn)/d $\equiv$ 1(mod n). 也就是說 m| a^$\phi$(mn)/d - 1 且 n| a^$\phi$(mn)/d - 1, 故再因 gcd(m, n) = 1 利用 Proposition 1.2.7(2) 可得 mn| a^$\phi$(mn)/d - 1, 即 a^$\phi$(mn)/d $\equiv$ 1(mod mn). 故依 order 之定義得 ord_mn(a)$\le$$\phi$(mn)/d. $\qedsymbol$

特別地, 假設 m 是一個大於 2 的整數. 若 m 沒有奇的質因數, 即 m = 2^k 其中 k$\ge$2. 此時 $\phi$(m) = $\phi$(2^k) = 2^{k - 1}, 故得 2|$\phi$(m). 若 m 有奇的質因數, 即存在一奇質數 p 使得 m = p^lm', 其中 l $\in$ $\mathbb {N}$ 且 p$\nmid$m'. 此時 $\phi$(m) = $\phi$(p^l)$\phi$(m') = (p - 1)p^{l - 1}$\phi$(m'), 同樣可得 2|$\phi$(m). 因此可知當 m, n > 2 時 gcd($\phi$(m),$\phi$(n))$\ge$2. 利用此一結果, 我們馬上可得另一個重要結論.

Proposition 6.2.4   當 m > 2 且 n > 2 為兩互質的整數時, 在 modulo mn 之下沒有 primitive root.

証 明. 因 m, n 皆大於 2 我們知 2|$\phi$(m) 且 2|$\phi$(n) 故得 gcd($\phi$(m),$\phi$(n))$\ge$2. 另一方面 m 和 n 是互質的, 故對任一與 mn 互質的整數 a, 由 Lemma 6.2.3 知

ord_mn(a)$$\le$$$${\frac{\phi(mn)}{\gcd(\phi(m),\phi(n))}}$$$$\le$$$${\frac{\phi(mn)}{2}}$$ < $$\phi$$(mn).

故知在 modulo mn 之下無 primitive root. $\qedsymbol$

當 m > 1 且沒有奇的質因數時, 我們知道當 m = 2, 4 時在 modulo m 之下有 primitive root, 而在其他狀況 (即 m = 2ⁿ 且 n$\ge$3) Proposition 6.2.2 告訴我們在 modulo m 之下沒有 primitive root. 當 m 有奇的質因數時, Proposition 6.2.4 告訴我們若 m 有兩個或兩個以上奇的質因數時, 在 modulo m 之下沒有 primitive root. 而當 m 只有一個奇的質因數時, Proposition 6.2.4 也告訴我們若 4| m, 在 modulo m 之下沒有 primitive root. 所以我們僅剩下 m 僅有一個奇的質因數且 4$\nmid$m 的情形未討論, 即 m = pⁿ 或 m = 2pⁿ, 其中 p 為奇質數的情形.