兩個處理 Diophantine Equations 的方法

我們簡單的介紹兩種處理 Diophantine equations 的方法. 這兩種方法都是用來處理 Diophantine equations 無解的情況.

第一種方法是用 congruence 的方法處理. 也就是說如果一個 Diophantine equation f (x₁,..., x_n) = 0 有整數解, 則對任意的 m $\in$ $\mathbb {N}$ 在 modulo m 之下 f (x₁,..., x_n) $\equiv$ 0(mod m) 當然有解. 因此若能找到一個 m 使得 f (x₁,..., x_n) $\equiv$ 0(mod m) 無解, 那麼原 Diophantine equation f (x₁,..., x_n) = 0 就無解.

Proposition 7.1.1   假設 f (x₁,..., x_n) 是一個整係數多項式. 若存在 m $\in$ $\mathbb {N}$ 使得 f (x₁,..., x_n) $\equiv$ 0(mod m) 無解, 則 f (x₁,..., x_n) = 0 無整數解.

証 明. 利用反證法假設 x₁ = c₁,..., x_n = c_n 是 f (x₁,..., x_n) = 0 的一組整數解. 由於 f (c₁,..., c_n) = 0, 自然有 f (c₁,..., c_n) $\equiv$ 0(mod m), 也就是說 x₁ = c₁,..., x_n = c_n 是 f (x₁,..., x_n) $\equiv$ 0(mod m) 的一組解. 此和 f (x₁,..., x_n) $\equiv$ 0(mod m) 無解的假設相矛盾故知 f (x₁,..., x_n) = 0 無整數解. $\qedsymbol$

要注意 Proposition 7.1.1 說的是若能找到一個 m $\in$ $\mathbb {N}$ 使得 f (x₁,..., x_n) $\equiv$ 0(mod m) 無解, 則 f (x₁,..., x_n) = 0 無整數解. 並不是說若能找到 m $\in$ $\mathbb {N}$ 使得 f (x₁,..., x_n) $\equiv$ 0(mod m) 有解, 則 f (x₁,..., x_n) = 0 有整數解. 千萬別搞錯了, 我們來看個例子.

Example 7.1.2   考慮 Diophantine equation 11x² - 7y² = 2. 在 modulo 11 之下, 我們要解 -7y² $\equiv$ 2(mod 11). 由於 -7×3 $\equiv$ 1(mod 11), -7y² $\equiv$ 2(mod 11) 兩邊乘上 3 可得 y² $\equiv$ 6(mod 11). 考慮 Legendre symbol $\left(\vphantom{\dfrac{{6}}{\,{11}\,}}\right.$${\dfrac{{6}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{6}}{\,{11}\,}}\right)$ = $\left(\vphantom{\dfrac{{2}}{\,{11}\,}}\right.$${\dfrac{{2}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{11}\,}}\right)$$\left(\vphantom{\dfrac{{3}}{\,{11}\,}}\right.$${\dfrac{{3}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{3}}{\,{11}\,}}\right)$. 由於 11 $\equiv$ 3(mod 4) 故由 Theorem 5.4.3 知 $\left(\vphantom{\dfrac{{2}}{\,{11}\,}}\right.$${\dfrac{{2}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{11}\,}}\right)$ = - 1 且由 Theorem 5.4.6 知 $\left(\vphantom{\dfrac{{3}}{\,{11}\,}}\right.$${\dfrac{{3}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{3}}{\,{11}\,}}\right)$ = - $\left(\vphantom{\dfrac{{11}}{\,{3}\,}}\right.$${\dfrac{{11}}{\,{3}\,}}$$\left.\vphantom{\dfrac{{11}}{\,{3}\,}}\right)$ = - $\left(\vphantom{\dfrac{{2}}{\,{3}\,}}\right.$${\dfrac{{2}}{\,{3}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{3}\,}}\right)$ = 1. 因此得 $\left(\vphantom{\dfrac{{6}}{\,{11}\,}}\right.$${\dfrac{{6}}{\,{11}\,}}$$\left.\vphantom{\dfrac{{6}}{\,{11}\,}}\right)$ = - 1, 也就是說 y² $\equiv$ 6(mod 11) 無解. 換言之, 11x² - 7y² - 2 $\equiv$ 0(mod 11) 無解, 因而由 Proposition 7.1.1 知 11x² - 7y² = 2 無整數解.

注意若將 11x² - 7y² = 2 考慮在 modulo 7 的情形, 也就是解 11x² $\equiv$ 2(mod 7). 由於 11×2 $\equiv$ 1(mod 7), 11x² $\equiv$ 2(mod 7) 兩邊乘上 2 得 x² $\equiv$ 4(mod 7). 很明顯的此式有 x $\equiv$ 2(mod 7) 為其解, 但由前已知 11x² - 7y² = 2 並無整數解. 所以由此例可知, 並不能因找到 m $\in$ $\mathbb {N}$ 使得 f (x₁,..., x_n) $\equiv$ 0(mod m) 有解, 便斷言 f (x₁,..., x_n) = 0 有解.

或許大家會好奇, 若對於任意的正整數 m, f (x₁,..., x_n) $\equiv$ 0(mod m) 皆有解, 是否就能得 f (x₁,..., x_n) = 0 有整數解呢? 由下面的例子我們可以知道, 這仍是不一定對的.

Example 7.1.3   令 f (x) = (x² - 17)(x² - 19)(x² - 323) 考慮 Diophantine equation f (x) = 0. 很明顯的這個 Diophantine equation 並無整數解. 但是我們將說明, 對任意 m $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod m) 皆有解.

由 Corollary 4.4.3 我們知道要證明對任意 m $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod m) 皆有解, 等同於要證明對任意質數 p 以及 n $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod pⁿ) 皆有解.

當 p = 2, n = 1 時, f (x) $\equiv$ (x² - 1)³(mod 2), 故 f (x) $\equiv$ 0(mod 2) 有解. 而當 p = 2, n = 2 時, f (x) $\equiv$ (x² - 1)(x² - 3)²(mod 4), 所以 f (x) $\equiv$ 0(mod 4) 亦有解. 當 p = 2, n$\ge$3 時, 由於 17 $\equiv$ 1(mod 8), Proposition 5.2.1 告訴我們 x² $\equiv$ 17(mod 2ⁿ) 必有解, 所以 f (x) = (x² - 17)(x² - 19)(x² - 323) $\equiv$ 0(mod 2ⁿ) 當然有解.

當 p = 17 時由於 17 $\equiv$ 1(mod 8), 故由 Theorem 5.4.3 知 x² $\equiv$ 19 $\equiv$ 2(mod 17) 有解. 因此由 Proposition 5.2.4 知對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ 19(mod 17ⁿ) 皆有解. 因此知 f (x) $\equiv$ 0(mod 17ⁿ) 有解. 而當 p = 19 時, 由於 17 $\equiv$ 1(mod 8) 故得 $\left(\vphantom{\dfrac{{17}}{\,{19}\,}}\right.$${\dfrac{{17}}{\,{19}\,}}$$\left.\vphantom{\dfrac{{17}}{\,{19}\,}}\right)$ = $\left(\vphantom{\dfrac{{19}}{\,{17}\,}}\right.$${\dfrac{{19}}{\,{17}\,}}$$\left.\vphantom{\dfrac{{19}}{\,{17}\,}}\right)$ = $\left(\vphantom{\dfrac{{2}}{\,{17}\,}}\right.$${\dfrac{{2}}{\,{17}\,}}$$\left.\vphantom{\dfrac{{2}}{\,{17}\,}}\right)$ = 1, 也就是說 x² $\equiv$ 17(mod 19) 有解. 再由 Proposition 5.2.4 知對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ 17(mod 19ⁿ) 皆有解. 因此知 f (x) $\equiv$ 0(mod 19ⁿ) 有解.

當 p 是奇質數且 p$\ne$17, 19 時, 若 x² $\equiv$ 17(mod p) 有解, 則 Proposition 5.2.4 告訴我們對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ 17(mod pⁿ) 亦有解. 所以此時 f (x) $\equiv$ 0(mod pⁿ) 有解. 同理若 x² $\equiv$ 19(mod p) 有解, 可得對任意 n $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod pⁿ) 亦有解. 而若 x² $\equiv$ 17(mod p) 和 x² $\equiv$ 19(mod p) 皆無解, 即 $\left(\vphantom{\dfrac{{17}}{\,{p}\,}}\right.$${\dfrac{{17}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{17}}{\,{p}\,}}\right)$ = $\left(\vphantom{\dfrac{{19}}{\,{p}\,}}\right.$${\dfrac{{19}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{19}}{\,{p}\,}}\right)$ = - 1, 則由 $\left(\vphantom{\dfrac{{232}}{\,{p}\,}}\right.$${\dfrac{{232}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{232}}{\,{p}\,}}\right)$ = $\left(\vphantom{\dfrac{{17}}{\,{p}\,}}\right.$${\dfrac{{17}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{17}}{\,{p}\,}}\right)$$\left(\vphantom{\dfrac{{19}}{\,{p}\,}}\right.$${\dfrac{{19}}{\,{p}\,}}$$\left.\vphantom{\dfrac{{19}}{\,{p}\,}}\right)$ = 1 知 x² $\equiv$ 232(mod p) 有解, 因此得對任意 n $\in$ $\mathbb {N}$, x² $\equiv$ 232(mod pⁿ) 皆有解. 我們仍得 f (x) $\equiv$ 0(mod pⁿ) 有解.

綜合以上結果我們知, 對任意質數 p 以及 n $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod pⁿ) 皆有解. 所以對任意 m $\in$ $\mathbb {N}$, f (x) $\equiv$ 0(mod m) 皆有解. 但是事實上 f (x) = 0 並沒有整數解.

再次強調一次, 我們介紹的 congruence 方法僅能拿來證明 Diophantine equation 無解. 所以若有一個 Diophantine equation 你認為它並無整數解, 那你可以考慮用 congruence 的方法去證明它無解. 也就是說試著找到一個 m $\in$ $\mathbb {N}$ 使其在 modulo m 之下無解, 那麼就證得此 Diophantine equation 無整數解. 若你認為一個 Diophantine equation 有解, 那麼 congruence 的方法頂多可以提供你其解的可能形式, 並無法告訴你原 Diophantine equation 有解.

另一種常用的方法稱為 descent 的方法. 它也是拿來證明一個 Diophantine equation 沒有正整數解. 其背後的原理是用到正整數的 well-ordering principle. 方法仍然是用反證法: 假設 Diophantine equation f (x₁,..., x_n) = 0 有正整數解且 x₁ = c₁,..., x_i = c_i,..., x_n = c_n 為其一組解. 若我們能利用 x₁ = c₁,..., x_i = c_i,..., x_n = c_n 這一組正整數解找到另一組正整數解 x₁ = c₁',..., x_i = c_i',..., x_n = c_n', 其中對某個特定 i $\in$ {1,..., n} 會有 c_i' < c_i, 則接下來可利用 x₁ = c₁',..., x_i = c_i',..., x_n = c_n' 這一組正整數解找到另一組正整數解 x₁ = c₁'',..., x_i = c_i'',..., x_n = c_n'' 滿足 c_i''<c_i'. 如此一直下去我們可得一個嚴格遞減的無窮正整數數列 c_i > c_i' > c_i''> ^... 此和正整數的 well-ordering principle 相違背, 故得證 f (x₁,..., x_n) = 0 沒有整數解.

以後我們會利用 descent 的方法證明某個有名的 Diophantine equation 無正整數解. 底下我們先舉一個簡單的例子讓大家了解 descent 的方法.

Example 7.1.4   大家都知道 $\sqrt{2}$ 是無理數, 所以我們可知 x² - 2y² = 0 這個 diophantine equation 無正整數解. 我們利用 descent 的方法來解釋 x² - 2y² = 0 無正整數解.

假設 x = c₁, y = d₁ 是 x² - 2y² = 0 的一組正整數解. 則由於 c₁² = 2d₁², 我們知 c₁ 必為正偶數, 也就是說存在 c₂ $\in$ $\mathbb {N}$ 使得 c₁ = 2c₂. 因此得 4c₂² = 2d₁², 即 2c₂² = d₁². 由此又得 d₁ 是正偶數, 故存在 d₂ $\in$ $\mathbb {N}$ 使得 d₁ = 2d₂. 因此得 2c₂² = 4d₂², 即 c₂² = 2d₂². 也就是說 x = c₂, y = d₂ 為 x² - 2y² = 0 的一組正整數解. 我們利用 x = c₁, y = d₁ 這一組正整數解得到 x = c₂, y = d₂ 這一組正整數解且滿足 c₁ > c₂, 故利用 descent 的方法知 x² - 2y² = 0 無正整數解.

這裡有一個邏輯上的問題需注意. 所謂 descent 的方法是指一個 Diophantine equation 若能證明「任給一組」正整數解都能產生另一組``較小"的正整數解, 則該 Diophantine equation 無正整數解. 僅由「特定的一組」正整數解可以得到另一組``較小"的正整數解並無法推得矛盾的結論. 例如 x = 8, y = 6, z = 10 是 x² + y² = z² 的一組正整數解, 將 x, y, z 皆除以 2 得 x = 4, y = 3, z = 5 也是 x² + y² = z² 的一組正整數解, 但此組解並不能再依此推得更小的一組解, 所以無法推得矛盾的結論. 事實上 x² + y² = z² 當然是有正整數解, 這並沒有和 descent 的方法相違背.