Order 與 Primitive Roots

給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$, 我們已知如何判別 x² $\equiv$ a(mod m) 有解或無解, 而 primitive root 的概念可以幫助我們找到解.

考慮 x² $\equiv$ 5(mod 11). 利用 quadratic reciprocity law 我們知 $\left(\vphantom{\dfrac{{5}}{\,{11}\,}}\right.$${\dfrac{{5}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{5}}{\,{11}\,}}\right)$ = $\left(\vphantom{\dfrac{{11}}{\,{5}\,}}\right.$${\dfrac{{11}}{\,{5}\,}}$$\left.\vphantom{\dfrac{{11}}{\,{5}\,}}\right)$ = $\left(\vphantom{\dfrac{{1}}{\,{5}\,}}\right.$${\dfrac{{1}}{\,{5}\,}}$$\left.\vphantom{\dfrac{{1}}{\,{5}\,}}\right)$ = 1, 故知 x² $\equiv$ 5(mod 11) 有解. 然而解為何呢? 我們可以利用 2 在 modulo 11 之下特有的性質幫助我們找解. 下表為 2ⁿ 在 modulo 11 的情形.

n	1	2	3	4	5	6	7	8	9	10
2n(mod 11)	2	4	8	5	10	9	7	3	6	1

我們發現第二行 (即 aⁿ 那一行) 中這 10 (= $\phi$(11)) 個數在 modulo 11 之下皆相異, 而且因 2 和 11 互質所以自然 2ⁿ 和 11 互質, 因此由 reduced residue system 的定義知 {2, 2²,..., 2¹⁰} 是一個 reduced residue system modulo 11. 這代表的意義是每個和 11 互質的數 a, 都可以找到 1$\le$n$\le$10 使得 a $\equiv$ 2ⁿ(mod 11). 另一方面我們僅將 n 列到 10 的原因是因為 2¹⁰ $\equiv$ 1(mod 11), 如果 m = 10k + i 其中 0$\le$i$\le$9, 則 2^m $\equiv$ 2ⁱ(mod 11). 也就是每 10 次方一循環, 所以列出 10 次就夠了. 又由於已知當 1$\le$i$\ne$j$\le$10 時, 2ⁱ $\not\equiv$2^j(mod 11), 我們知 2ⁱ $\equiv$ 2^j(mod 11) 若且唯若 i $\equiv$ j(mod 10). 結合這些結果可以幫助我們解 x² $\equiv$ 5(mod 11). 原因如下: 假設 x = c 是一解, 由於 5 和 11 互質, 故知 c 和 11 互質. 因此知存在 t $\in$ $\mathbb {N}$ 使得 c $\equiv$ 2^t(mod 11). 然而 5 $\equiv$ 2⁴(mod 11), 故由 2^2t $\equiv$ c² $\equiv$ 5 $\equiv$ 2⁴(mod 11) 得 2t $\equiv$ 4(mod 10). 我們很巧妙的將解二次的 x² $\equiv$ 5(mod 11) 轉化成解一次的 2t $\equiv$ 4(mod 10) (注意 modulo 不同的數). 故利用 Proposition 4.2.1 解得 t $\equiv$ 2(mod 5), 也就是說 t = 2, 7,... 為 2t $\equiv$ 4(mod 10) 之解. 將之代回 c = 2^t, 得 c $\equiv$ 4, 7(mod 11). 故知 x $\equiv$ ±4(mod 11) 為 x² $\equiv$ 5(mod 11) 之解.

可依此法解二次 congruence equation 歸功於在 modulo 11 之下 {2, 2²,..., 2¹¹} 是 reduced residue system. 要注意並不是 2 永遠有此特性. 例如 2³ $\equiv$ 1(mod 7), 所以 {2, 2²,..., 2⁶} 在 modulo 7 之下並不是 reduced residue system. 我們將有此特性的元素給個特定的名子.

Definition 6.1.1   給定 m $\in$ $\mathbb {N}$, 若 a $\in$ $\mathbb {Z}$ 且與 m 互質滿足 {a, a²,..., a^$\phi$(m)} 是一個 reduced residue system modulo m, 則稱 a 為 modulo m 之下的一個 primitive root.

要注意並不是對所有的 m 皆有 primitive root. 例如在 modulo 15 之下, 所有和 15 互質的數 a 皆有 a⁴ $\equiv$ 1(mod 15), 所以又因 a^$\phi$(15) = a⁸ $\equiv$ 1(mod 15) 知 {a, a², a³, a⁴,..., a⁸} 不可能形成 reduced residue system modulo 15. 也就是說在 modulo 15 之下並無 primitive root. 我們最主要的目的就是要探討哪些 m $\in$ $\mathbb {N}$ 在 modulo m 之下會有 primitive root.

首先我們必須了解怎樣的 a 在 modulo m 之下會是 primitive root. 由於 S = {a, a²,..., a^$\phi$(m)} 是 reduced residue system modulo m, 所以若 1$\le$i$\ne$j$\le$$\phi$(m), 則 aⁱ $\not\equiv$a^j(mod m). 否則 S 在 modulo m 之下會有少於 $\phi$(m) 個同餘類, 無法形成 reduced residue system modulo m. 然而 a 和 m 互質, Euler's Theorem (3.3.2) 告訴我們 a^$\phi$(m) $\equiv$ 1(mod m), 所以 a 在 modulo m 之下是 primitive root 的先決條件是若 1$\le$i$\le$$\phi$(m) - 1, 則 aⁱ $\not\equiv$1(mod m) (否則會造成 1$\le$i < $\phi$(m) 且 aⁱ $\equiv$ a^$\phi$(m)(mod m) 的矛盾). 也就是說滿足 aⁿ $\equiv$ 1(mod m) 的最小正整數 n 為 n = $\phi$(m). 因此給定 a $\in$ $\mathbb {Z}$ 且 gcd(a, m) = 1, 最小的正整數 n 滿足 aⁿ $\equiv$ 1(mod m) 為何, 是判斷 a 在 modulo m 之下是否為 primitive root 的重要依據. 我們自然有以下之定義.

Definition 6.1.2   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 若 n $\in$ $\mathbb {N}$ 是最小的正整數滿足 aⁿ $\equiv$ 1(mod m), 則稱 n 為 a 在 modulo m 之下的 order, 並以 ord_m(a) = n 表之.

要注意由於 gcd(a, m) = 1, Euler's Theorem 告訴我們 a^$\phi$(m) $\equiv$ 1(mod m), 所以 ord_m(a) 必存在且依定義知 ord_m(a)$\le$$\phi$(m). 首先我們來看依定義馬上可得之性質.

Lemma 6.1.3   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1.

1. 若 a $\equiv$ b(mod m) 則 ord_m(a) = ord_m(b).
2. ord_m(a) = 1 若且唯若 a $\equiv$ 1(mod m).

証 明. (1) 若 a $\equiv$ b(mod m), 知對任意 i $\in$ $\mathbb {N}$ 皆有 aⁱ $\equiv$ bⁱ(mod m), 故若 n 是最小的正整數使得 aⁿ $\equiv$ 1(mod m), 則 n 也會是最小的正整數使得 bⁿ $\equiv$ 1(mod m). 因此知 ord_m(a) = ord_m(b).

(2) 若 ord_m(a) = 1, 表示 a¹ $\equiv$ 1(mod m), 故得 a $\equiv$ 1(mod m). 反之, 若 a $\equiv$ 1(mod m), 當然 n = 1 是最小的正整數使得 aⁿ $\equiv$ 1(mod m), 故知 ord_m(a) = 1. $\qedsymbol$

其實 order 的定義和最大公因數的定義類似, 我們要說 ord_m(a) = n 等於要說兩件事:

1. aⁿ $\equiv$ 1(mod m).
2. 若 1$\le$i$\le$n - 1, 則 aⁱ $\not\equiv$1(mod m).

要記住這兩件事缺一不可才能保證 ord_m(a) = n. 接下來我們就來看依此兩點可推得 ord_m(a) 的性質.

Proposition 6.1.4   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 假設 ord_m(a) = n. 則 a^k $\equiv$ 1(mod m) 若且唯若 n| k.

証 明. 假設 a^k $\equiv$ 1(mod m). 利用 Division Algorithm (Theorem 1.2.1) 知存在 h, r $\in$ $\mathbb {Z}$ 滿足 k = nh + r, 其中 0$\le$r$\le$n - 1. 由 aⁿ $\equiv$ 1(mod m) 知 a^k = a^{nh + r} = (aⁿ)^ha^r $\equiv$ a^r(mod m). 現假設 r$\ne$ 0 (即 1$\le$r$\le$n - 1), 則由 a^k $\equiv$ 1(mod m) 之假設知 a^r $\equiv$ 1(mod m). 此和 n 是最小的正整數滿足 aⁿ $\equiv$ 1(mod m) 相違背, 故知 r = 0, 即 n| k.

反之若 n| k, 即存在 h $\in$ $\mathbb {Z}$ 滿足 k = nh, 故得 a^k = a^nh = (aⁿ)^h $\equiv$ 1(mod m). $\qedsymbol$

若 a 和 m 互質, Euler's Theorem 告訴我門 a^$\phi$(m) $\equiv$ 1(mod 1), 故由 Proposition 6.1.4 知 ord_m(a)|$\phi$(m), 這比我們前面依定義知 ord_m(a)$\le$$\phi$(m) 好多了. 同樣的, 利用 Proposition 6.1.4, 我們可以有更好的方式來判定 ord_m(a) 之值.

Corollary 6.1.5   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 則 ord_m(a) = n 若且唯若 n 滿足以下兩條件:

1. aⁿ $\equiv$ 1(mod m).
2. 若 a^k $\equiv$ 1(mod m), 則 n| k.

証 明. 若 ord_m(a) = n, 則自然有 aⁿ $\equiv$ 1(mod m), 再利用 Proposition 6.1.4 知, 若 a^k $\equiv$ 1(mod m), 則 n| k.

反之若 n 滿足 (1),(2) 兩項, 我們要證明 ord_m(a) = n. 由於 (1) 已知 aⁿ $\equiv$ 1(mod m), 故僅剩要證明若 1$\le$i$\le$n - 1, 則 aⁱ $\not\equiv$1(mod m). 我們用反證法, 假設 aⁱ $\equiv$ 1(mod m), 則由 (2) 知 n| i. 此和 1$\le$i$\le$n - 1 相矛盾, 故知 aⁱ $\not\equiv$1(mod m). 也就是說 ord_m(a) = n. $\qedsymbol$

Corollary 6.1.5 的 (2) 將 ord_m(a) = n 原本表最小的正整數滿足 aⁿ $\equiv$ 1(mod m) 的性質轉換成看似更強的性質 (就如同當初原本最大公因數是最大的公因數可轉換成為所有的公因數的倍數這樣的性質) 在以後有關 order 的理論推導中有很大的幫助.

計算 order 的另一個重要的原因是我們可以知道 aⁱ 在 modulo m 之下的週期.

Proposition 6.1.6   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 假設 ord_m(a) = n 且 i, j $\in$ $\mathbb {N}$. 則 aⁱ $\equiv$ a^j(mod m) 若且唯若 i $\equiv$ j(mod n).

証 明. 假設 aⁱ $\equiv$ a^j(mod m), 不失一般性我們也假設 i$\ge$j, 此時 aⁱ - a^j = a^j(a^{i - j} - 1). 利用 m| aⁱ - a^j 以及 m 和 a^j 互質 (因 m 和 a 互質), Proposition 1.2.7 告訴我們 m| a^{i - j} - 1, 即 a^{i - j} $\equiv$ 1(mod m). 故利用 ord_m(a) = n 以及 Proposition 6.1.4 知 m| i - j, 亦即 i $\equiv$ j(mod n).

反之, 若 i $\equiv$ j(mod n), 不失一般性我們假設 i$\ge$j, 則有 n| i - j. 故再利用 Proposition 6.1.4 知 a^{i - j} $\equiv$ 1(mod m). 兩邊乘上 a^j 因此有 aⁱ = a^ja^{i - j} $\equiv$ a^j(mod m). $\qedsymbol$

若 ord_m(a) = n, Proposition 6.1.6 不只告訴我們 a, a²,..., aⁱ,... 在 modulo m 之下的週期為 n (即每隔 n 個 i, aⁱ 會形成一循環) 而且告訴我們, a, a²,..., aⁿ 在 modulo m 之下皆相異. 否則若存在 1$\le$j < i$\le$n 使得 aⁱ $\equiv$ a^j(mod m), 可得 n| i - j 而與 0 < i - j < n - 1 相矛盾. 依此我們可以確定可以用 ord_m(a) 之值來判定 a 在 modulo m 之下是否為 primitive root.

Corollary 6.1.7   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 則 ord_m(a) = $\phi$(m) 若且唯若 a 在 modulo m 之下是一個 primitive root.

証 明. 假設 a 是 modulo m 之下的一個 primitive root. 由於 a, a²,..., a^$\phi$(m) 在 modulo m 之下皆不同餘, 故知若 1$\le$i$\le$$\phi$(m), 則 aⁱ $\not\equiv$a^$\phi$(m)(mod m). 又由於 Euler's Theorem 知 a^$\phi$(m) $\equiv$ 1(mod m), 故知 ord_m(a) = $\phi$(m).

反之, 假設 ord_m(a) = $\phi$(m), 由 Proposition 6.1.6 知若 aⁱ $\equiv$ a^j(mod m), 則 $\phi$(m)| i - j. 因此 a, a²,..., a^$\phi$(m) 在 modulo m 之下皆不同餘. 又由於 a 和 m 互質, 知 aⁱ 皆與 m 互質, 故 {a, a²,..., a^$\phi$(m)} 是一個 reduced residue system modulo m, 也就是說 a 在 modulo m 之下是一個 primitive root. $\qedsymbol$

若已知 a 在 modulo m 的 order, 則對任意 i $\in$ $\mathbb {N}$, 利用 Corollary 6.1.5 我們都可算出 aⁱ 在 modulo m 之下的 order.

Proposition 6.1.8   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 若 ord_m(a) = n, 則對於任意的正整數 i,

ord_m(aⁱ) = $${\frac{n}{\gcd(i,n)}}$$.

証 明. 為了方便, 我們令 d = gcd(i, n). 欲證明 ord_m(aⁱ) = n/d, 首先得證明 (aⁱ)^n/d $\equiv$ 1(mod m). 事實上因為 d 是 i 的因數, i/d 是個整數. 再加上由假設 ord_m(a) = n, 故 aⁿ $\equiv$ 1(mod m). 所以可得

(aⁱ)^n/d = (aⁿ)^i/d $$\equiv$$ 1(mod m).

接下來我們須證明, 若 (aⁱ)^k $\equiv$ 1(mod m) 則 (n/d ) | k (參見 Corollary 6.1.5(2)). 若 (aⁱ)^k $\equiv$ 1(mod m), 即 a^ki $\equiv$ 1(mod m). 故由 Proposition 6.1.4, 我們可得 n | ki. 但因 d 是 n 和 i 的最大公因數. 我們有 n/d 和 i/d 皆為整數且互質. 故由 n | ki 可得 (n/d ) | k(i/d ). 再由 n/d 和 i/d 互質, 得 (n/d ) | k. $\qedsymbol$

由 Proposition 6.1.8, 我們知 ord_m(aⁱ) 整除 ord_m(a) 而且 ord_m(aⁱ) = ord_m(a) 若且唯若 gcd(i,ord_m(a)) = 1. 因此在 modulo m 之下 primitive root 若存在, 則我們可推知在 modulo m 之下會有多少個 primitive roots.

Corollary 6.1.9   給定 m $\in$ $\mathbb {N}$ 以及 a $\in$ $\mathbb {Z}$ 滿足 gcd(a, m) = 1. 若 ord_m(a) = n, 則 {a, a²,..., aⁿ} 中共有 $\phi$(n) 個元素其在 modulo m 之下的 order 為 n. 特別地, 若在 modulo m 之下 primitive root 是存在的, 則在 modulo m 之下共有 $\phi$($\phi$(m)) 個 primitive roots.

証 明. 已知 ord_m(a) = n, 由 Proposition 6.1.8 知 ord_m(aⁱ) = n 若且唯若 gcd(n, i) = 1. 又由於 a, a²,..., aⁿ 在 modulo m 之下皆相異, 故 {a, a²,..., aⁿ} 中在 modulo m 之下 order 為 n 的元素個數等於和 n 互質且小於 n 的正整數的個數, 依定義知此數為 $\phi$(n).

現假設在 modulo m 之下有 primitive root 且 a 為一個 primitive root. 故知 ord_m(a) = $\phi$(m) 且所有和 m 互質的整數在 modulo m 之下皆和 S = {a, a²,..., a^$\phi$(m)} 中某個元素同餘. 所以在 modulo m 之下所有的 primitive root 皆可在 S 中找到. 然而由前知 S 中共有 $\phi$($\phi$(m)) 個元素其在 modulo m 之下的 order 為 $\phi$(m), 且 Corollary 6.1.7 告訴我們在 modulo m 之下只有這些元素為 primitive root. 故知在 modulo m 之下共有 $\phi$($\phi$(m)) 個 primitive roots. $\qedsymbol$