二次 Congruence Equation 的化簡

所謂二次的 congruence equation, 即給定 m $\in$ $\mathbb {N}$, 考慮 ax² + bx + c $\equiv$ 0(mod m), 其中 a, b, c $\in$ $\mathbb {Z}$ 且 m$\nmid$a 這樣的 equation.

大家看到這樣的方程式, 首先會想到用配方法來解. 沒錯, 我們也是要用配方法. 不過這裡有一點要特別注意, 就是我們都是在整數的情況, 所以須避免用到除法. 例如大家要解 ax² + bx + c = 0 時, 第一個想到的是將 x² 項的係數 a 除去得 x² + (b/a)x + (c/a) = 0. 由於我們在談 congruence equation, 多項式需要求為整係數, 這個方法就行不通了 (除非 a| b 且 a| c). 當然了, 當 a 和 m 互質時存在 e $\in$ $\mathbb {Z}$ 使得 ae $\equiv$ 1(mod m), 所以此時我們可以將 ax² + bx + c $\equiv$ 0(mod m) 兩邊乘上 e 而得 x² + bex + ce $\equiv$ 0(mod m). 不過這個方法要限制在 gcd(m, a) = 1 的情形, 而我們要探討的是一般情況, 所以我們需想辦法處理. 不管怎樣為了讓多項式為整係數, 我們不要用除的方法, 儘量用乘的. 所以為了使用配方法我們可以讓 x² 項係數成為完全平方, 也就是將 ax² + bx + c $\equiv$ 0(mod m) 兩邊乘上 a 而得 (ax)² + abx + ac $\equiv$ 0(mod m). 接著處理 x 項係數, 由於不能用除的所以不能將 abx 寫成 2(ab/2)x, 但用配方法 x 項係數需偶數, 因此好的方法是將原式兩邊乘以 2. 不過這樣一來又破壞了原先 x² 項係數為完全平方的好處, 所以我們再多乘一個 2 使得 x² 項係數仍為完全平方.

也就是說, 在解 ax² + bx + c $\equiv$ 0(mod m) 時我們可以將兩邊乘上 4a 使得原式成為 4a²x² + 4abx + 4ac = (2ax)² + 2(2ax)b + 4ac $\equiv$ 0(mod m). 接下來就可用配方法常用步驟將式子寫成 (2ax + b)² $\equiv$ b² - 4ac(mod m). 因此我們將問題簡化成解 y² $\equiv$ b² - 4ac(mod m). 今若沒有整數 k 滿足 k² $\equiv$ b² - 4ac(mod m), 那麼我們便知原 congruence equation, ax² + bx + c $\equiv$ 0(mod m) 無解. 若可找到 k $\in$ $\mathbb {Z}$ 滿足 k² $\equiv$ b² - 4ac(mod m), 那麼我們便可依前面探討一次的 congruence equation 的方法解 2ax + b $\equiv$ k(mod m), 而得到 ax² + bx + c $\equiv$ 0(mod m) 解之情況.

總之, 解二次 congruence equation, ax² + bx + c $\equiv$ 0(mod m) 的問題, 可化簡成解 y² $\equiv$ d(mod m) 其中 d = b² - 4ac. 因此我們接下來僅探討 x² $\equiv$ a(mod m) 這樣的 congruence equation.

假設 m = p₁^{n₁ ...} p_t^n_r, 其中這些 p_i 為相異質數. 由 Corollary 4.4.3 知, x² $\equiv$ a(mod m) 有解若且唯若對所有的 p_i, x² $\equiv$ a(mod p_i^n_i) 有解. 因此我們又將問題化簡為求 x² $\equiv$ a(mod pⁿ), 其中 p 為質數且 n $\in$ $\mathbb {N}$ 的情形.

我們來看一個綜合以上結果的例子.

Example 5.1.1   我們試著解 29x² + 15x + 1 $\equiv$ 0(mod 45). 首先將式子兩邊乘上 4×29, 得 (58x)² + 2×58×15x + 116 $\equiv$ 0(mod 45). 接著利用配方法得 (58x + 15)² $\equiv$ 109(mod 45), 即 (13x + 15)² $\equiv$ 19(mod 45) (別忘了 58x $\equiv$ 13x(mod 45)).

接著因為 45 = 3²×5, 我們可以將式子轉化成解 (13x + 15)² $\equiv$ 19(mod 9) 及 (13x + 15)² $\equiv$ 19(mod 5). 也就是說分別解 (4x + 6)² $\equiv$ 1(mod 9) 以及 (3x)² $\equiv$ 4(mod 5). 由於 y $\equiv$ ±1(mod 9) 為 y² $\equiv$ 1(mod 9) 之解, 故知 4x + 6 $\equiv$ ±1(mod 9), 解得 x $\equiv$ 1, 5(mod 9) 為 (13x + 15)² $\equiv$ 19(mod 9) 之解. 另一方面 y $\equiv$ ±2(mod 5) 為 y² $\equiv$ 4(mod 5) 之解, 故得 3x $\equiv$ ±2(mod 5), 解得 x $\equiv$ 1, 4(mod 5) 為 (13x² + 15)² $\equiv$ 19(mod 5) 之解.

最後要解 29x² + 15x + 1 $\equiv$ 0(mod 45), 由前知 x 需符合:

(1)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 1 & \hbox{$\pmod{9}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 1 & \hbox{$\pmod{9}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}$$,(2)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 1 & \hbox{$\pmod{9}$} \\ x\equiv 4 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 1 & \hbox{$\pmod{9}$} \\ x\equiv 4 & \hbox{$\pmod{5}$} \\ \end{array}$$,

(3)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 5 & \hbox{$\pmod{9}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 5 & \hbox{$\pmod{9}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}$$ 或 (4)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 5 & \hbox{$\pmod{9}$} \\ x\equiv 4 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 5 & \hbox{$\pmod{9}$} \\ x\equiv 4 & \hbox{$\pmod{5}$} \\ \end{array}$$.

因此求得 x $\equiv$ 1, 14, 19, 41(mod 45) 為 29x² + 15x + 1 $\equiv$ 0(mod 45) 之解.

回到我們的主題. 我們將要解一般二次的 congruence equation 化解成解 x² $\equiv$ a(mod pⁿ), 其中 p 為質數且 n $\in$ $\mathbb {N}$ 的情形. 我們先來看 a 和 p 不互質的情形. 假設 pⁿ| a 等於解 x² $\equiv$ 0(mod pⁿ), 此時當然有解. 若 a = pⁱa' 其中 p$\nmid$a' 且 1$\le$i$\le$n - 1 怎麼辦? 現假若 i 是奇數, 我們要說明此時 x² $\equiv$ pⁱa'(mod pⁿ) 無解. 若有解且 b 為 x² $\equiv$ pⁱa'(mod pⁿ) 之一解, 我們將 b 寫成 b = p^sb', 其中 p$\nmid$b'. 此時因假設 b² $\equiv$ pⁱa'(mod pⁿ), 可得 pⁿ| p^2sb'² - pⁱa'. 由於 2s 是偶數而 i 是奇數, 知 2s$\ne$i. 如果 2s > i, 則 p^2sb'² - pⁱa' = pⁱ(p^{2s - i}b'² - a'). 但由於 p| p^{2s - i} 且 p$\nmid$a', 我們知 p$\nmid$p^{2s - i}b'² - a'. 換言之 p^{i + 1}$\nmid$p^2sb'² - pⁱa'. 此和 pⁿ| p^2sb'² - pⁱa' 且 n$\ge$i + 1 相矛盾. 同理, 若 2s < i, 我們也可得矛盾的情形. 所以當 i < n 且是奇數時 x² $\equiv$ pⁱa'(mod pⁿ) 無解.

當 a = pⁱa' 其中 p$\nmid$a', 0 < i < n 且 i = 2k 是偶數時, 若我們將 x 寫成 x = p^kt, 此時解 x² $\equiv$ a(mod pⁿ) 等同於解 (p^kt)² $\equiv$ p^2ka'(mod pⁿ), 也就是解 p^2kt² $\equiv$ p^2ka'(mod pⁿ). 由於 2k < n, Proposition 4.2.1 告訴我們此式等同於解 t² $\equiv$ a'(mod p^{n - 2k}). 我們將以上討論寫成結論.

Proposition 5.1.2   給定一質數 p 及 n $\in$ $\mathbb {N}$. 假設 a = pⁱa' 其中 p$\nmid$a' 且 1$\le$i$\le$n - 1.

1. 若 i 是奇數, 則 x² $\equiv$ a(mod pⁿ) 無解.
2. 若 i 是偶數, 則 x² $\equiv$ a(mod pⁿ) 有解若且唯若 x² $\equiv$ a'(mod p^{n - i}) 有解.

從以上的討論我們知道要解一個二次的 congruence equation 都可以簡化到 x² $\equiv$ a(mod pⁿ), 其中 p$\nmid$a 的情況. 所以以後我們僅專注於 x² $\equiv$ a(mod pⁿ) 其中 p$\nmid$a 的情形.