高次的 Congruence Equation

所謂高次的 congruence equation 指的是次數大於 2 的 congruence equation. 我們這裡要處理的當然不是一般的 congruence equation. 我們想利用 primitive root 來幫我們解如 xⁿ $\equiv$ a(mod m) 其中 gcd(a, m) = 1 這樣的 congruence equation.

首先我們將 m 寫成質因數的乘積, 即 m = 2^n₀p₁^{n₁ ...} p_r^n_r, 其中這些 p_i 為相異奇質數而 n₀$\ge$ 0. 利用 Corollary 4.4.3, 我們知道 xⁿ $\equiv$ a(mod m) 有解若且唯若 xⁿ $\equiv$ a(mod 2^n₀) 以及所有的 i $\in$ {1..., r}, xⁿ $\equiv$ a(mod p_i^n_i) 皆有解. 所以我們只要探討 xⁿ $\equiv$ a(mod 2^n₀) 及 xⁿ $\equiv$ a(mod p_i^n_i) 解的情況. 當 n₀$\ge$3 時, 由於在 modulo 2^n₀ 沒有 primitive root, 討論解的情形較複雜, 這裡我們不多做討論. 我們僅討論當 n₀$\le$2 的情形, 也就是說此處我們探討解 xⁿ $\equiv$ a(mod m) 的方法僅適用於 8$\nmid$m 的情況. 在此情況之下我們只要解 xⁿ $\equiv$ a(mod 2^n₀), 其中 n₀$\le$2, 以及解 xⁿ $\equiv$ a(mod p_i^n_i). 這兩種情況 (即 modulo 2^n₀ 和 modulo p_i^n_i), 由於 primitive root 皆存在, 我們利用下面的方法就可判別其解是否存在.

Theorem 6.4.1   給定 m $\in$ $\mathbb {N}$, 假設在 modulo m 之下 primitive root 存在. 考慮 xⁿ $\equiv$ a(mod m), 其中 n $\in$ $\mathbb {N}$ 且 gcd(a, m) = 1. 令 d = gcd(n,$\phi$(m)). 則 xⁿ $\equiv$ a(mod m) 有解若且唯若

a^$\phi$(m)/d $$\equiv$$ 1(mod m).

証 明. 首先假設 xⁿ $\equiv$ a(mod m) 有解, 即存在 c $\in$ $\mathbb {Z}$ 滿足 cⁿ $\equiv$ a(mod m). 因為 gcd(a, m) = 1, 所以 gcd(c, m) = 1, 故由 Euler's Theorem (3.3.2) 知 c^$\phi$(m) $\equiv$ 1(mod m). 此時由於 d|$\phi$(m) 且 d| n, 故得

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

(注意此部分的證明是不需 modulo m 的 primitive root 存在之假設.)

反之, 假設 $\gamma$ 為 modulo m 之下的一個 primitive root. 依定義 {$\gamma$,$\gamma^{2}_{}$,...,$\gamma^{\phi(m)}_{}$} 是一個 reduced residue system modulo m, 也就是說任何和 m 互質的數 b, 皆存在 i $\in$ $\mathbb {N}$ 使得 $\gamma^{i}_{}$ $\equiv$ b(mod m). 因此存在 r $\in$ $\mathbb {N}$ 使得 a $\equiv$ $\gamma^{r}_{}$(mod m). 另一方面若 c 是 xⁿ $\equiv$ a(mod m) 的一個解, 則由於 gcd(c, m) = 1, 一定也存在 t $\in$ $\mathbb {N}$ 使得 c $\equiv$ $\gamma^{t}_{}$(mod m). 因此要解 xⁿ $\equiv$ a(mod m) 就等同於要找到 t $\in$ $\mathbb {N}$ 使得

($$\gamma^{t}_{}$$)ⁿ = $$\gamma^{nt}_{}$$ $$\equiv$$ $$\gamma^{r}_{}$$(mod m).

由於 $\gamma$ 是 modulo m 的 primitive root, 我們有 ord_m($\gamma$) = $\phi$(m), 故利用 Proposition 6.1.6, 知 $\gamma^{nt}_{}$ $\equiv$ $\gamma^{r}_{}$(mod m) 若且唯若 nt $\equiv$ r(mod $\phi$(m)), 也就是說我們要找到 t $\in$ $\mathbb {N}$ 滿足

nt $$\equiv$$ r(mod $$\phi$$(m)).

另一方面依假設 a^$\phi$(m)/d $\equiv$ 1(mod m), 即 $\gamma^{r\phi(m)/d}_{}$ $\equiv$ 1(mod m), 故由 Proposition 6.1.4 知 $\phi$(m)| r$\phi$(m)/d. 這表示 $\phi$(m)r/d 必須是 $\phi$(m) 的倍數, 亦即 r/d $\in$ $\mathbb {Z}$, 也就是說 d| r. 然而 Proposition 4.3.1 告訴我們給定 n, r, 一次的 congruence equation, nt $\equiv$ r(mod $\phi$(m)) 有解若且唯若 d = gcd(n,$\phi$(m))| r. 所以我們由 a^$\phi$(m)/d $\equiv$ 1(mod m) 之假設知 nt $\equiv$ r(mod $\phi$(m)) 必有解. 若 t₀ 為其一解, 令 c = $\gamma^{t_0}_{}$, 則得

cⁿ = $$\gamma^{nt_0}_{}$$ $$\equiv$$ $$\gamma^{r}_{}$$ $$\equiv$$ a(mod m).

故知 c 為 xⁿ $\equiv$ a(mod m) 的一個解. $\qedsymbol$

當 m = p 為一質數 (此時 modulo p 當然有 primitive root) 且 n = 2 時, Theorem 6.4.1 就是 Euler's criterion (Theorem 5.3.3). 所以 Theorem 6.4.1 可以說是 Theorem 5.3.3 的推廣.

接下來我們要知道 xⁿ $\equiv$ a(mod m) 要是有解, 那麼在 modulo m 之下會有多少解. 和往常一樣, 我們所用的方法是直接探討兩個解之間的關係, 如此一來不只可以精確地算出解的個數, 而且可以很快的利用一個已知解將其他的解求出.

Proposition 6.4.2   給定 m $\in$ $\mathbb {N}$, 假設在 modulo m 之下 primitive root 存在. 考慮 xⁿ $\equiv$ a(mod m), 其中 n $\in$ $\mathbb {N}$ 且 gcd(a, m) = 1. 令 d = gcd(n,$\phi$(m)). 若 xⁿ $\equiv$ a(mod m) 有解, 則在 modulo m 之下共有 d 個解.

事實上, 若 x $\equiv$ c(mod m) 是 xⁿ $\equiv$ a(mod m) 的一個解且 $\gamma$ 是 modulo m 之下的一個 primitive root, 則在 modulo m 之下 x $\equiv$ c$\gamma^{t\phi(m)/d}_{}$(mod m), 其中 t $\in$ {0, 1,..., d - 1} 是 xⁿ $\equiv$ a(mod m) 所有的解.

証 明. 由於 a 和 m 互質, xⁿ $\equiv$ a(mod m) 的解皆與 m 互質. 又由於 $\gamma$ 是 modulo m 之下的一個 primitive root, 所以對於 xⁿ $\equiv$ a(mod m) 的任兩個解, 我們可假設其分別為 $\gamma^{r}_{}$ 和 $\gamma^{s}_{}$, 其中 r, s $\in$ $\mathbb {N}$. 也就是說

$$\gamma^{rn}_{}$$ = ($$\gamma^{r}_{}$$)ⁿ $$\equiv$$ a $$\equiv$$ ($$\gamma^{s}_{}$$)ⁿ $$\equiv$$ $$\gamma^{sn}_{}$$(mod m).

因此利用 ord_m($\gamma$) = $\phi$(m) 以及 Proposition 6.1.6 得 rn $\equiv$ sn(mod $\phi$(m)). 因此由於 d = gcd(n,$\phi$(m)) 依 Proposition 3.2.3 知 r $\equiv$ s(mod $\phi$(m)/d). 也就是說存在 $\lambda$ $\in$ $\mathbb {Z}$ 使得 s = r + $\lambda$$\phi$(m)/d. 反之, 若 $\gamma^{r}_{}$ 是 xⁿ $\equiv$ a(mod m) 的一個解且 s = r + $\lambda$$\phi$(m)/d, 則

($$\gamma^{s}_{}$$)ⁿ = ($$\gamma^{r}_{}$$$$\gamma^{\lambda\phi(m)/d}_{}$$)ⁿ = $$\gamma^{rn}_{}$$$$\gamma^{\lambda\phi(m)n/d}_{}$$ $$\equiv$$ a ($$\gamma^{\phi(m)}_{}$$)^$\lambda$n/d $$\equiv$$ a(mod m).

因此 $\gamma^{s}_{}$ 也是 xⁿ $\equiv$ a(mod m) 的一個解.

我們證得了若 x $\equiv$ c $\equiv$ $\gamma^{r}_{}$(mod m), 是 xⁿ $\equiv$ a(mod m) 的一個解, 則 x $\equiv$ c$\gamma^{\lambda\phi(m)/d}_{}$(mod m), 其中 $\lambda$ $\in$ $\mathbb {Z}$, 是 xⁿ $\equiv$ a(mod m) 所有的解. 不過這些解在 modulo m 之下有許多是相同的, 我們必須將有哪些相異解找出. 然而 c 和 m 互質, 故由 Corollary 3.2.4知 c$\gamma^{\lambda\phi(m)/d}_{}$ $\equiv$ c$\gamma^{\lambda'\phi(m)/d}_{}$(mod m) 若且唯若 $\gamma^{\lambda\phi(m)/d}_{}$ $\equiv$ $\gamma^{\lambda\phi(m)/d}_{}$(mod m). 再利用 ord_m($\gamma$) = $\phi$(m) 以及 Proposition 6.1.6 知 $\gamma^{\lambda\phi(m)/d}_{}$ $\equiv$ $\gamma^{\lambda'\phi(m)/d}_{}$(mod m) 若且唯若 $\lambda$$\phi$(m)/d $\equiv$ $\lambda{^\prime}$$\phi$(m)/d(mod $\phi$(m)) 也就是說 $\phi$(m)|($\lambda$ - $\lambda{^\prime}$)$\phi$(m)/d 亦即 d|$\lambda$ - $\lambda{^\prime}$. 因此當 0$\le$t$\le$d - 1 時, c$\gamma^{t\phi(m)/d}_{}$ 在 modulo m 之下皆相異. 另一方面對任意 $\lambda$ $\in$ $\mathbb {Z}$ 皆存在 h, t $\in$ $\mathbb {Z}$ 使得 $\lambda$ = hd + t, 其中 0$\le$t$\le$d - 1. 所以 c$\gamma^{\lambda\phi(m)/d}_{}$ 在 modulo m 之下都會與某個 c$\gamma^{t\phi(m)/d}_{}$ 同餘, 其中 t $\in$ {0, 1,..., d - 1}. 因此我們得證 xⁿ $\equiv$ a(mod m) 若有 x $\equiv$ c(mod m) 這一個解 則在 modulo m 之下 xⁿ $\equiv$ a(mod m) 共有 x $\equiv$ c, c$\gamma^{\phi(m)/d}_{}$, c$\gamma^{2\phi(m)/d}_{}$,..., c$\gamma^{(d-1)\phi(m)/d}_{}$ 這 d 個解. $\qedsymbol$

接下來我們利用一個實際的例子解釋 Proposition 6.4.1 和 Proposition 6.4.2 所得之結果.

Example 6.4.3   我們來探討 x¹² $\equiv$ 10(mod 27) 和 x¹² $\equiv$ 11(mod 27) 解的情形.

由於 27 = 3³ 所以在 modulo 27 之下 primitive root 是存在的. 又 $\phi$(27) = 18 且 gcd(12,$\phi$(27)) = gcd(12, 18) = 6 利用 Proposition 6.4.1 我們可分別由 10^$\phi$(27)/6 = 10³ 和 11³ 在 modulo 27 是否為 1 來判定 x¹² $\equiv$ 10(mod 27) 和 x¹² $\equiv$ 11(mod 27) 是否有解. 事實上 10³ $\equiv$ 1(mod 27) 且 11³ $\equiv$ 8 $\not\equiv$1(mod 27), 所以 x¹² $\equiv$ 10(mod 27) 有解而 x¹² $\equiv$ 11(mod 27) 無解.

要找出 x¹² $\equiv$ 10(mod 27) 的解, 首先需先找到 modulo 27 的一個 primitive root. 由於 2 是 modulo 3 的 primitive root 且 2² $\equiv$ 4 $\not\equiv$1(mod 9), 所以由 Lemma 6.3.4 知 2 在 modulo 9 是 primitive root. 因而由 Proposition 6.3.7 知 2 在 modulo 27 之下依然是 primitive root. 既然 2 是 modulo 27 的一個 primitive root 經計算我們知 2⁶ $\equiv$ 10(mod 27) 且可以將 x¹² $\equiv$ 10(mod 27) 的一解寫成 x $\equiv$ 2^t(mod 27) 的形式. 也就是說我們要解

(2^t)¹² $$\equiv$$ 2⁶(mod 27).

因此由 ord₂₇(2) = $\phi$(27) = 18 以及 Proposition 6.1.6 知此等價於解

12t $$\equiv$$ 6(mod 18).

故由 gcd(18, 12) = 6 得 2t $\equiv$ 1(mod 3), 即 t $\equiv$ 2(mod 3). 解出 x $\equiv$ 2² $\equiv$ 4(mod 27) 為 x¹² $\equiv$ 10(mod 27) 的一個解. 再由 $\phi$(27)/6 = 3 以及 Proposition 6.4.2 知 x $\equiv$ 4, 4×2³, 4×2⁶, 4×2⁹, 4×2¹², 4×2¹⁵(mod 27), 即 x $\equiv$ 4, 5, 13, 23, 22, 14(mod 27) 為 x¹² $\equiv$ 10(mod 27) 所有的解. 事實上我們也可以由 12t $\equiv$ 6(mod 18) 找到 t $\equiv$ 2, 5, 8, 11, 14, 17(mod 18) 為其所有的解, 而得 x $\equiv$ 2², 2⁵, 2⁸, 2¹¹, 2¹⁴, 2¹⁷(mod 27) 為 x¹² $\equiv$ 10(mod 27) 所有的解.