工欲善其事，必先利其器——從一道數論題談起

05-24

來自專欄愛哞客棧

這是一道很有爭議的問題，對它的評價也五花八門。這題的結論非常漂亮，但是《走向 IMO 2006》公布的兩個解答對讀者卻不太友好。一個過於晦澀冗長，而另一個卻過於精妙。它們的共同點是讀者難以參透其中的奧妙。這道題獲得了當年的最佳命題獎，同時也創造了最低得分率的記錄（總共 4 人得分，分別是 21 分、兩人 9 分、3 分）。有人說這題的知識點和技巧並不在常見的競賽大綱之內，也有人說用初等的方法解決高等的問題才是數學競賽的魅力所在。它就是：

例（2006 年全國中學生數學冬令營的第 3 題）正整數 $m, n, k$ 滿足 $mn=k^2+k+3$ ，證明不定方程 $x^2+11y^2=4m$ 和 $x^2+11y^2=4n$ 中至少有一個有奇數解 $(x,y)$ 。

我今年在講授抽象代數的過程中，無意間發現這道題其實是代數數論的一個簡單推論，愛哞客棧便希望我來寫一篇關於這道題背後的故事。其實一開始我覺得並不合適。一方面是不可避免地要使用高等的語言和結論，在競賽考場上不具有可操作性。另一方面是當年唯一的一位滿分選手鄧煜也是專欄作者，由我來寫這篇文章難免有越俎代庖之嫌。後來經過歸納整理，從代數數論中來的結論可以完全封裝成「唯一因子分解定理」直接使用，而剩下的推理分析完全是初等的。另外，作為在考場上獲得 9 分的選手之一，我當時的解答更接近於標答里的解法一，可以給大家展示一下兩個標答背後的思路。我們將盡量迴避高等的語言以免增加讀者的負擔，並在解答中力圖解釋每一步背後的來龍去脈。對高等背景感興趣的同學，可以參考 Artin 所著 Algebra 第二版第 13 章。

在應用熟知的技巧來解這道題之前，讓我們先來看看我們究竟需要什麼。注意到 $x^2+11y^2=4m$ 等價於 $(x+sqrt{-11}y)(x-sqrt{-11}y)=4m$ 。換句話說，如果我們適當擴大整數的範圍，使之包含 $sqrt{-11}$ 的話，那方程有解相當於說 $4m$ 在擴大化的整數里能夠分解成兩個模長相等的因子的乘積。所以，我們真正需要的是一套整除理論，它同時覆蓋整數和 $sqrt{-11}$ 。我們將用它來分析 $4m$ 和 $4n$ 的因子分布情況。那首當其衝的問題就是這套整除理論建立在哪裡。第一選擇當然是集合 $mathbb{Z}[sqrt{-11}]={a+bsqrt{-11}mid a,binmathbb{Z}}$ ，因為它包含整數和 $sqrt{-11}$ 。它可以定義加法減法乘法，有交換結合分配律，但沒有除法。從運算性質來看，它完全可以類比為整數。如果我們能理解它上面的整除性和「素因子分解」，那麼無疑對於解決問題會很有幫助。但是，它的「素因子分解」並不是唯一的！比如我們有 $2^2 imes 3=(1+sqrt{-11})(1-sqrt{-11})$ ，並且不難證明左右兩邊都無法繼續分解了。唯一分解性的缺失會造成很多意想不到的麻煩。為了克服這個困難，我們轉而考慮以下這個集合

$left{frac{a+bsqrt{-11}}{2} : aequiv b extrm{ (mod }2) ight}$

並把它記作 $R$ 。我們至少有兩方面的理由來說明 $R$ 比 $mathbb{Z}[sqrt{-11}]$ 更好。一方面，條件 $mn=k^2+k+3$ 在 $R$ 中可以自然地分解為

$mn=left(k+frac{1+sqrt{-11}}{2} ight)left(k+frac{1-sqrt{-11}}{2} ight).$

我們要解的方程也能寫作

$frac{x+sqrt{-11}y}{2}cdotfrac{x-sqrt{-11}y}{2}=m$

$frac{x+sqrt{-11}y}{2}cdotfrac{x-sqrt{-11}y}{2}=n,$

成功避開了 4 這個因子帶來的干擾。與此同時，要證明方程存在奇數解與 $R$ 中的要求分子同奇同偶也有著微妙的聯繫。另一方面， $R$ 是滿足「唯一因子分解」這個性質的，而 $mathbb{Z}[sqrt{-11}]$ 不滿足。唯一因子分解性保證我們繼續分解 $m, n, k+({1pmsqrt{-11}})/2$ 之後， $mn$ 和 $k^2+k+3$ 的素因子以及重數是相同的，而這將是我們證明的立足點。讀者或許會疑惑我們為何一直用 $sqrt{-11}$ 這個奇怪的記號，而沒有使用更常見的 $sqrt{11}i$ 。這是因為我們試圖強調 $sqrt{-11}$ 在 $R$ 中，而 $sqrt{11}$ 和 $i$ 都不在。所以我們完全看不見 $sqrt{11}$ 和 $i$ ，只有當它們乘在一起的時候才在我們的考慮範圍之內。

面對 $R$ 這麼一個陌生的對象，如果它的性質和整數類似那就最好了，這樣來自於整數的直觀將極大地幫助我們思考。為了區分，我們把 $R$ 中的數稱為元素，簡稱元。我們羅列一些基本概念和性質，以保證在 $R$ 中也可以討論「整除」和「素因子」，並且它們具有和整數中類似的性質。

$R$ 中有加法減法乘法，滿足一切整數所滿足的運算性質：交換律，結合律，分配律，存在加法單位元 0，乘法單位元 1，每個元素 $x$ 存在負元 $-x$ 。在這些性質中，唯一不顯然的是 $R$ 中任意兩個元素的積仍在 $R$ 中。比如兩個分母為 2 的乘積分母可以是 4，但這在 $R$ 中是不被允許的。通過簡單的計算可以發現，在定義 $x=(a+bsqrt{-11})/2$ 中 $a, b$ 的同奇同偶的要求保證這不會發生。
$R$ 中可以研究整除關係。對於 $R$ 中的元素 $alpha$ 和 $eta$ ，記號 $alphamideta$ 意味著存在 $R$ 中元素 $gamma$ 使得 $eta=alphagamma$ 。
$R$ 中僅有的乘法可逆元只有 1 和 -1，這和整數是一樣的。
$R$ 中的元素 $alpha$ 被稱為素元，如果它具有性質：如果 $alphamidetagamma$ ，那麼 $alphamideta$ 或者 $alphamidgamma$ 。這個定義和整數中素數的性質是一樣的。
$R$ 中的元素 $alpha$ 被稱為不可約元，如果它具有性質：如果 $alpha=etagamma$ ，那麼 $eta=pm1$ 或者 $gamma=pm1$ 。這個定義和整數中素數的定義是一樣的。
$R$ 中的因子分解總是有限長的，即 $R$ 中的任何元素 $x$ 至多能寫成有限多個非 0 和 ±1 的元素乘積。這是因為 $R$ 中的元素除了 0 和 ±1 以外，（視為複數的）模長都不小於 2，而模長是可乘的。
在 $R$ 里，素元和不可約元是等價的概念，和整數的情形一樣。這個結論來自於代數數論，我們把它當做一個黑箱子直接使用就好。
$R$ 有唯一因子分解性。嚴格地來說， $R$ 中任意一個非零元素 $x$ 可以寫成寫成有限個素元的乘積 $alpha_1cdotsalpha_n$ 。這些素元（允許重複）在不計正負號和順序的意義下是唯一決定的。事實上，在滿足因子分解有限長的條件下，滿足唯一因子分解性當且僅當素元和不可約元是等價的概念。

從這些術語和性質上來看， $R$ 中的素因子分解和整數 $mathbb{Z}$ 中的分解並沒有本質的不同。我們完全可以借鑒整數的經驗來指導我們對 $R$ 的研究。讀者可能覺得這隻有理論上的可能性，其實不然。讓我們回憶一下在自然數中，我們習以為常的素因子分解是怎麼進行的。首先我們用篩法來構造素數表：1 不是素數劃掉，2 是素數留下，划去其餘 2 的倍數，然後 3 是素數留下，划去所有 3 的倍數，4 已被划去，然後留下 5，以此類推。而素因子分解是從最小的素數開始依次試除。在 $R$ 里我們同樣可以這麼做：我們把所有的元素模長從小到大排城一列（允許相等），用篩法獲得素元表，然後用模長從小到大試除來進行素因子分解。在這個過程中，我們需要用到了 $R$ 中的非零元素模長都至少是 1，並且模長為 1 的情形只在 ±1 取到這兩條性質，以保證在做試除的時候，越除模長越小，並且有限步必將終止。與此同時，我們還用到了試除的順序是沒有影響的，這由唯一因子分解性保證。請注意，如果不是在 $R$ 中，而是在 $mathbb{Z}[sqrt{-11}]$ 中，素元和不可約元這兩個概念是不一樣的！我們舉一些例子來說明它們的差異，以及在 $R$ 中為何差異又消失了。

在 $mathbb{Z}[sqrt{-11}]$ 中，2 是一個不可約元，但是 2 不是一個素元。因為在我們之前的例子中， $2^2 imes 3=(1+sqrt{-11})(1-sqrt{-11})$ 。所以 $2mid(1+sqrt{-11})(1-sqrt{-11})$ ，但 2 不整除其中任何一個。這個問題在 $R$ 中被解決了：在 $R$ 中，2 同時整除它們兩個。所以 2 在 $R$ 中既是素元又是不可約元。
在 $mathbb{Z}[sqrt{-11}]$ 中，3 是一個不可約元，但 3 不是一個素元，理由同上。但是在 $R$ 中，3 不是不可約元，因為 $3=(1+sqrt{-11})/2cdot(1-sqrt{-11})/{2}$ 。在 $R$ 中 3 也不是素元，因為 $3mid(1+sqrt{-11})(1-sqrt{-11})$ 但 3 不整除其中任何一個。
在 $mathbb{Z}[sqrt{-11}]$ 中無法繼續分解的 $2^2 imes 3=(1+sqrt{-11})(1-sqrt{-11})$ 在 $R$ 中可以進一步分解為 $2cdot 2 cdot (1+sqrt{-11})/{2}cdot(1-sqrt{-11})/{2}=2cdot(1+sqrt{-11})/{2}cdot2cdot(1-sqrt{-11})/{2}$ 。從而在不計順序的意義下，兩邊的分解是相同的！
我們利用 $R$ 的性質來看一個複雜一些的例子： $2^25^2=(1+3sqrt{-11})(1-3sqrt{-11})$ 。我們知道 $R$ 有唯一因子分解性。所以兩邊必然能繼續分解直到相同。首先把兩個因子 2 除到右邊，我們有 $5^2=(1+3sqrt{-11})/{2}cdot(1-3sqrt{-11})/{2}$ 。注意到 5 不整除右邊的任何一項，這意味著 5 在 $R$ 中不是素元。從而它不是不可約元，一定可以繼續分解。假設 $alpha=(a+bsqrt{-11})/2$ 是 5 的一個真因子。那麼 $ar{alpha}=({a-bsqrt{-11}})/{2}$ 也是 5 的真因子。這樣 $alphaar{alpha}=({a^2+11b^2})/{4}$ 是 25 的真因子。由於它是正的，只可能是 5。我們得到 $a^2+11b^2=20$ 。從而 $a=pm3, b=pm1$ 。所以左邊等於
$left(frac{3+sqrt{-11}}{2}cdotfrac{3-sqrt{-11}}{2} ight)^2.$
不難驗證， $(3pmsqrt{-11})/2$ 已經是不可約元了。這意味著左邊的四項必將重新組合得到等式右邊的兩項。計算可知
$left(frac{3pmsqrt{-11}}{2} ight)^2=-frac{1mp 3sqrt{-11}}{2}.$

所以兩邊給出的 25 在 $R$ 中的素因子分解在不計順序和符號的意義下是唯一的。

細心的讀者或許已經發現，我們將 5 在 $R$ 中繼續分解的時候，解了方程 $a^2+11b^2=4cdot5$ 。這個方程和原題的形式是完全一樣的，連繫數都絲毫不差。結論是 5 可以繼續分解當且僅當這個方程有解。這啟發我們去研究 $m$ 的素數因子 $p$ 視為 $R$ 中的元素的時候，它是否仍然是一個素元，如果不是，那繼續分解的形態又是怎樣的。事實上，我們有如下這個重要的結論，它刻畫出了 $R$ 中素元和 $mathbb{Z}$ 中素數的聯繫。它們的證明並不難，我們留給讀者思考。

設 $alpha$ 為 $R$ 中的一個素元。那麼或者 $alpha$ 是 $mathbb{Z}$ 中的一個素數（不計正負的意義下）或者 $alphaar{alpha}$ 是 $mathbb{Z}$ 中的一個素數。
設 $p$ 是一個 $mathbb{Z}$ 中的素數. 那麼或者 $p$ 是 $R$ 中的素元，或者存在 $R$ 中的素元 $alpha$ ，使得 $p=alphaar{alpha}$ 。這裡 $alpha$ 在不計共軛和正負的意義下唯一（ $R$ 有唯一因子分解性）。

有了以上的準備，我們可以來解決原問題了。注意到條件 $mn=k^2+k+3$ 等價於

$mn=left(k+frac{1+sqrt{-11}}{2} ight)left(k+frac{1-sqrt{-11}}{2} ight).$

在研究方程整數解的時候，這樣的分解本來是沒有意義的，但是我們把研究範圍擴大到了 $R$ ，這就是一個再正常不過的分解了。我們把等式兩邊都繼續分解為素因子的乘積。根據唯一因子分解性，兩邊在不計符號不計順序的意義下必須是相同的。這樣右邊 $k+({1pmsqrt{-11}})/{2}$ 特殊的形式將對出現可能出現的素因子產生限制，進而決定 $m$ 和 $n$ 的可能有哪些素因子，而這些素因子又直接決定了方程有沒有解。接下來我們講實現這個思路。首先我們整數範圍內分解 $m=p_1p_2cdots$ （允許重複）。如果 $p_i$ 在 $R$ 中是素元，則保留，如果不是，那麼它一定是某個素元和它共軛的乘積。這樣，最終的分解是 $m=p_1cdots p_ualpha_1cdotsalpha_sar{alpha}_1cdotsar{alpha}_s$ 。對 $n$ 也作類似的分解 $n=q_1cdots q_veta_1cdotseta_tar{eta}_1cdotsar{eta}_t$ 。乘在一起我們有

$left(k+frac{1+sqrt{-11}}{2} ight)left(k+frac{1-sqrt{-11}}{2} ight)=p_1cdots p_u q_1cdots q_valpha_1cdotsalpha_sar{alpha}_1cdotsar{alpha}_seta_1cdotseta_tar{eta}_1cdotsar{eta}_t$

我們斷言 $u=v=0$ ，即 $m$ 和 $n$ 在整數中的那些素因子在 $R$ 中必須全部繼續分解。如若不然，假設素數 $p$ 在 $R$ 中仍是一個素元並出現在分解中。那麼 $pmid k+(1+sqrt{-11})/{2}$ 或者 $pmid k+({1-sqrt{-11}})/{2}$ 。無論是哪種情況，根據 $R$ 中整除的定義，我們總有 $pmid 2k+1$ 且 $pmid 1$ ，這是不可能的。所以我們有 $m=alpha_1cdotsalpha_sar{alpha}_1cdotsar{alpha}_s$ 和 $n=eta_1cdotseta_tar{eta}_1cdotsar{eta}_t$ 。記 $(a+bsqrt{-11})/{2}=alpha_1cdotsalpha_s$ ，則 $m=({a+bsqrt{-11}})/{2}cdot({a-bsqrt{-11}})/{2}$ ，從而就有 $4m=a^2+11b^2$ 。對 $n$ 也有類似的結論。這裡，我們證明了兩個方程必須同時有整數解。

要證明兩個方程中至少有一個有奇數解，我們還需要作更仔細的分析。我們回到分解

$left(k+frac{1+sqrt{-11}}{2} ight)left(k+frac{1-sqrt{-11}}{2} ight)=alpha_1cdotsalpha_sar{alpha}_1cdotsar{alpha}_seta_1cdotseta_tar{eta}_1cdotsar{eta}_t$

根據唯一因子分解性，右邊的素因子將重新組合得到左邊兩個括弧內的數（不計正負的意義下）。我們希望對所有的 $i$ 都有 $alpha_i$ 和 $ar{alpha}_i$ 分屬左邊的兩個括弧，對 $eta_j$ 和 $ar{eta_j}$ 也是這樣。事實上，這幾乎是顯然的。一方面是我們之前已經證了 $k+({1pmsqrt{-11}})/{2}$ 並不能有非正負 1 的正整數的因子，這意味著 $alpha_i$ 和 $ar{alpha}_i$ 不能整除左邊的同一個數。另一方面是因為 $alpha_imid k+({1+sqrt{-11}})/{2}$ 等價於 $ar{alpha}_imid k+({1-sqrt{-11}})/{2}$ 。唯一需要注意的是分解中可能出現重因子，同時 $k+({1+sqrt{-11}})/{2}$ 和 $k+({1-sqrt{-11}})/{2}$ 也可以有公因子。這個小麻煩不難解決，處理方法也很多。比如我們可以在最一開始的時候就做得仔細些：把 $m$ 在整數中分解為 $p_1cdots p_s$ ，根據已證的結論， $p_1$ 在 $R$ 中分解為共軛的兩個素元的乘積。我們把整除 $k+({1+sqrt{-11}})/{2}$ 的那個記作 $alpha_1$ ，另一個記作 $ar{alpha_1}$ 。在分解 $p_2$ 的時候，我們要求 $alpha_2mid left(k+({1+sqrt{-11}})/{2} ight)/alpha_1$ ，然後以此類推。對 $eta_j$ 也類似處理。這樣做的好處是，唯一因子分解性保證了我們一定有 $k+({1+sqrt{-11}})/{2}=pmalpha_1cdotsalpha_seta_1cdotseta_t$ 。我們仍然記 $({a+bsqrt{-11}})/{2}=alpha_1cdotsalpha_s$ 以及 $({c+dsqrt{-11}})/{2}=eta_1cdotseta_t$ 。那麼我們有 $4m=a^2+11b^2$ 以及 $4n=c^2+11d^2$ 的同時，我們還有一個新的等式

$frac{a+bsqrt{-11}}{2}cdotfrac{c+dsqrt{-11}}{2}=pmleft(k+frac{1+sqrt{-11}}{2} ight).$

這意味著 $ac-11bd=pm2(2k+1)$ 以及 $ad+bc=pm2$ 。這說明 $a,b,c,d$ 不能都是偶數，從而至少有一個方程有奇數解，證畢。

讓我們來回顧一下。在解決這個問題的過程中，我們的著手點是對 $x^2+11y^2=4m$ 類型的方程進行完整的分析。首先我們在 $R$ 上建立了一套整除理論，並給出了構造素元表和進行素因子分解的構造。接下來我們通過對 5 進行素因子分解意識到 $x^2+11y^2=4m$ 的解完全由 $4m$ 在 $R$ 中進行素因子分解決定。然後條件 $mn=k^2+k+3$ 保證 $m$ 的素數因子在 $R$ 中必須全部繼續分解，而這一點事實上等價於 $x^2+11y^2=4m$ 有解。事實上，我們不難得到這個方程的所有解：在 $m$ 每一組共軛的素元中選一個，把他們乘起來並寫成 $left(a+bsqrt{-11} ight)/{2}$ 的形式，則 $(a,b)$ 就是一組解，而所有的解都可以用此法得到。這裡我們還證明了無論如何，兩個方程必須同時有整數解。接著我們說明其中一種特殊的選法，使得兩個方程的整數解之間還滿足兩個額外的等式，奇數解的存在性正是這兩個額外等式的副產品。

根據上面的解答，我們可以在《走向 IMO 2006》標答中背後發現一些端倪。這裡我們只是試圖用反推的方法分析一下思路。在這個過程中，我們也可以看到初等方法中的技巧在相當程度上可以替代來自於高等的背景知識。

摘自《走向 IMO 2006》第 30 至 33 頁

證法一引理中描述的事實是 $x^2+11y^2=4m$ 或者有奇數解，或者有滿足 $x_0equiv(2k+1)y_0 extrm{ (mod }m)$ 的偶數解。而這一組偶數解 $(x_0,y_0)$ 將給出 $x^2+11y^2=4n$ 的奇數解，化簡以後可以寫成

$(x_1,y_1)=left(frac{11y_0+(2k+1)x_0}{2m},frac{x_0-(2k+1)y_0}{2m} ight).$

通過直接計算，兩個方程的解之間滿足的關係正如我們所預期： $x_0x_1-11y_0y_1=2(2k+1)$ ， $x_0y_1+x_1y_0=2$ 。換言之，從引理得到最終結果恰好用了這兩個額外的等式。而在引理中的證明中，應用抽屜原理的技巧在與二次剩餘相關的初等數論問題中是很常見的。比如可以用來證明如下的結論：對於素數 $p>3$ ， $p=x^2+3y^2$ 有整數解當且僅當 $pequiv1 extrm{ (mod }3)$ 。必要性是顯然的。充分性的做法是當 $pequiv1 extrm{ (mod }3)$ 時，二次互反律保證了存在整數 $a$ 使得 $a^2equiv-3 extrm{ (mod } p)$ 。考慮所有如下的表示 $s+ta$ ，其中 $0le s,tle [sqrt{p}]$ 。注意到總共有 $left(lfloorsqrt{p} floor+1 ight)^2>p$ 個表示，從而必然有兩個關於 $p$ 同餘。於是 $s_1+t_1aequiv s_2+t_2a extrm{ (mod }p)$ ，移項以後有 $s_1-s_2equiv a(t_2-t_1) extrm{ (mod }p)$ 。平方並注意到 $a^2equiv-3 extrm{ (mod }p)$ ，我們就有 $(s_1-s_2)^2+3(t_2-t_1)^2equiv0 extrm{ (mod }p)$ 。同樣由於 $s$ 和 $t$ 的選取， $(s_1-s_2)^2+3(t_2-t_1)^2<p+3p=4p$ 。模 3 即可知道 $2p$ 是取不到的，而取到 $3p$ 的時候意味著 $3|s_1-s_2$ ， $(t_2-t_1)^2+3(frac{s_1-s_2}{3})^2=p$ 給出了一組解。

摘自《走向 IMO 2006》第 34 至 36 頁

在證法二中，我們注意到解答用歸納法證明的結論和我們的觀點非常類似：首先兩個方程必須都有整數解，並且它們的整數解之間有著極其緊密的聯繫：它們滿足額外的兩個方程。是的，它們又一次出現了。所以這個解答完整地刻畫了這兩個不定方程整數解的信息，使得巧妙歸納法成為可能。當然這僅僅是基於我們的解答所作的反推與猜測，或許原作者鄧煜會在評論里談談他在考場上是怎麼想出來的呢。

最後說說我的想法。這次的專欄文章和一年前的組合恆等式之萬金油方法或許會讓讀者誤以為我是特別熱衷於用高等黑科技來解決競賽題的選手。其實並不是這樣。我欣賞用一種看得見摸得著的，可重複利用的思路去解決一類問題，去發現問題的本質結構，而不是就題論題地用靈光一現的技巧去繞開問題的內核。當然從命題角度來說，為了一道本來並不困難的題而去建立一套理論完全沒有必要。而隱藏某些高等背景，將定理初等化作為考題在我看來也不值得推崇。用烹飪來打個比方，廚藝好比解題能力和技巧，而原材料好比是各種背景知識。能用最簡單的食材做出美味佳肴，這當然是最好的。但如果你真的一定要考驗我在蘿蔔片上鑽圓孔的刀功，那我覺得還是直接去買藕比較好。