p 為奇質數的情形

當 p 是奇質數時, 我們當然不能如 p = 2 的情形討論. 不過由 Lemma 4.2.2 我們知若 x² $\equiv$ a(mod p) 無解, 則對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ a(mod pⁿ) 亦無解. 我們要用數學歸納法證明若 x² $\equiv$ a(mod p) 有解, 則對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ a(mod pⁿ) 亦有解.

Proposition 5.2.4   假設 p 為一奇質數且 p$\nmid$a. 則 x² $\equiv$ a modp 有解若且唯若對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ a(mod pⁿ) 有解.

証 明. 我們僅要證明若 x² $\equiv$ a(mod p) 有解則 x² $\equiv$ a(mod pⁿ) 亦有解.

若 c 為 x² $\equiv$ a(mod p) 之一解, 即存在 $\lambda$ $\in$ $\mathbb {Z}$ 使得 c² = a + $\lambda$p. 現考慮 c' = c + tp. 由於 c'² = c² + 2ctp + t²p² = a + (2ct + $\lambda$)p + t²p². 若要 c'² $\equiv$ a(mod p²), 則需找到 t $\in$ $\mathbb {Z}$ 使得 2ct $\equiv$ - $\lambda$(mod p). 然而由於 2c 和 p 互質, Theorem 4.3.3 告訴我們這樣的 t 一定存在. 故此時若令 c' = c + tp, 則 x $\equiv$ c'(mod p²) 為 x² $\equiv$ a(mod p²) 之一解.

現利用數學歸納法假設 n = k - 1 (k$\ge$2) 時 x² $\equiv$ a(mod p^{k - 1}) 有解, 且假設 x $\equiv$ c(mod p^{k - 1}) 為其一解. 我們想利用 c 找到 x² $\equiv$ a(mod p^k) 的解. 由於存在 $\lambda$ $\in$ $\mathbb {Z}$ 使得 c² - a = $\lambda$p^{k - 1}, 我們考慮 c' = c + tp^{k - 1}. 此時 c'² = c² + 2ctp^{k - 1} + t²p^{2k - 2} = a + (2ct + $\lambda$)p^{k - 1} + t²p^{2k - 2}. 由於 2k - 2 = k + k - 2$\ge$k (因 k$\ge$2) 我們得 c'² $\equiv$ a + (2ct + $\lambda$)p^{k - 1}(mod p^k). 又因為 2c 和 p 互質, 故存在 t' $\in$ $\mathbb {Z}$ 使得 2ct' + $\lambda$ $\equiv$ 0(mod p). 此時若令 c' = c + t'p, 則 x $\equiv$ c'(mod p^k) 為 x² $\equiv$ a(mod p^k) 之一解. $\qedsymbol$

如果 x² $\equiv$ a(mod pⁿ) 有解, 我們當然有興趣知道在 modulo pⁿ 之下, x² $\equiv$ a(mod pⁿ) 其解的個數.

Proposition 5.2.5   假設 p 為一奇質數, p$\nmid$a 且 n $\in$ $\mathbb {N}$. 若 x² $\equiv$ a modpⁿ 有解且 x $\equiv$ c(mod pⁿ) 為其一解, 則 x $\equiv$ ±c(mod pⁿ) 為 x² $\equiv$ a(mod pⁿ) 所有的解.

証 明. 假設 c' 為 x² $\equiv$ a(mod pⁿ) 之另一解, 知 pⁿ| c² - c'². 由於 c 和 c' 皆與 p 互質, c + c' 和 c - c' 知中必有一個與 p 互質, 否則由 p| c + c' 及 p| c - c' 可得 p| 2c, 而又 p$\ne$2, 可得 p| c 之矛盾. 現假設 c + c' 與 p 互質, 此時 gcd(c + c', pⁿ) = 1, 故由 pⁿ|(c + c')(c - c') 及 Proposition 1.2.7(1), 得知 pⁿ| c - c', 即 c' $\equiv$ c(mod pⁿ). 同理, 若 c - c' 與 p 互質, 可得 c' $\equiv$ - c(mod pⁿ).

另一方面, 由 c² $\equiv$ a(mod pⁿ) 知 (- c)² = c² $\equiv$ a(mod pⁿ), 故知 x $\equiv$ ±c(mod pⁿ) 為 x² $\equiv$ a(mod pⁿ) 所有的解. $\qedsymbol$

我們再來看個例子.

Example 5.2.6   解 x² $\equiv$ 14(mod 125). 由於 x² $\equiv$ 14 $\equiv$ 4(mod 5) 有解 (x = 2 為一解), 由 Proposition 5.2.4 知 x² $\equiv$ 14(mod 125) 必有解. 我們利用 Proposition 5.2.4 證明中所用的方法來找出一個解. 首先找出 x² $\equiv$ 14(mod 25) 之ㄧ個解. 利用 2 為 x² $\equiv$ 14(mod 5) 之一解, 考慮 (2 + 5t)² = 4 + 20t + 25t². 因此 (2 + 5t)² - 14 $\equiv$ - 10 + 20t(mod 25). 也就是說需解出 t $\in$ $\mathbb {Z}$ 使得 20t $\equiv$ 10(mod 25), 即解 4t $\equiv$ 2(mod 5). 可得 t = 3 為一解, 故帶入 2 + 5t 得 x = 17 為 x² $\equiv$ 14(mod 25) 之一解. 現再利用 17 求 x² $\equiv$ 14(mod 125) 之一解. 考慮 (17 + 25t)² = 289 + 850t + 625t². 因此 (17 + 25t)² - 14 $\equiv$ 275 + 850t $\equiv$ 25 + 100t(mod 125). 也就是說需解出 t $\in$ $\mathbb {Z}$ 使得 100t $\equiv$ - 25(mod 125), 即解 4t $\equiv$ - 1(mod 5). 可得 t = 1 為一解, 故帶入 17 + 25t 得 x = 42 為 x² $\equiv$ 14(mod 125) 之一解. 找到一解後, 最後利用 Proposition 5.2.2 知 x $\equiv$ ±42(mod 125) 為 x² $\equiv$ 14(mod 125) 所有的解.

我們已完全了解 x² $\equiv$ a(mod 2ⁿ) 的解的情況. 而當 p 是奇質數時, 對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ a(mod pⁿ) (其中 p$\nmid$a) 的解的情況完全取決於 x² $\equiv$ a(mod p) 的解的情況. 所以以後我們僅專注於 x² $\equiv$ a(mod p) 其中 p 為奇質數且 p$\nmid$a 的情形.