中國剩餘定理(the CRT)與拉格朗日插值法(Lagrange's interpolation)

《孫子算經》中有一道題：

今有物，不知其數。三、三數之，賸二；五、五數之，賸三；七、七數之，賸二。問物幾何？

相傳漢帝劉邦欲在酒席間趁機抓拿韓信，問韓信有帶多少兵，沒料到韓信未正面回覆，僅說了他的兵士，若三個三個一數，會餘兩個，五個五個一數，會餘三個，七個七個一數，會餘兩個。劉邦摸不著頭序，不知若是此時抓了韓信，會不會反被他的將士抓了，韓信於是逃過一劫。

這就是著名的「韓信點兵」，當然也有其他不同的故事說法，但無論如何，它正是中國剩餘定理(the Chinese Remainder Theorem, the CRT)名稱的由來。

如果先考慮簡單一點的問題：若三個三個一數，只餘一個，五個五個一數與七個七個一數都剛好數完，那麼，只要從5×7的倍數中：35、70、105、140、…，找到被3除餘1的，如70，那麼70再加減3×5×7的倍數，就會是答案，即70+105k，其中k為整數。

如果三個三個一數，餘兩個，五個五個一數與七個七個一數都剛好數完。就只要把上一則的70乘以2，再加減3×5×7的倍數，就會是答案，即2×70+105k，其中k為整數。

用同樣的方法，若要找三個三個一數會數完，五個五個一數餘三，七個七個一數也剛好數完，則從3×7的倍數中找到被5除餘1的數，例如21，再把21乘以3，加減3×5×7的倍數即可，即3×21+105k，其中k為整數。

同理，若要找三個三個一數與五個五個一數都會數完，但七個七個一數餘二的數，則從3×5的倍數中找到被7除餘1的數，例如15，再把15乘以2，加減3×5×7的倍數即可，即2×15+105k，其中k為整數。

為什麼要算上面這幾道題呢，因為只要把上面的2×70、3×21、2×15加起來，再加減3×5×7的倍數，就會是上面《孫子算經》的題目或是韓信點兵的答案了。也就是說，韓信帶的兵，應該是2×70+3×21+2×15=233再加減3×5×7的倍數，所以很有可能韓信只帶了233−2×105=23個士兵。

我們把上面的題目歸納成一般的結果，也就是中國剩餘定理：

假設m₁、m₂、m₃、…、m_n兩兩互質，且整數x被m₁除餘r₁，被m₂除餘r₂，被m₃除餘r₃，…，被m_n除餘r_n。則x有無限多解，且求解的方法為：找出(m₁·m₂·m₃·…·m_n)/m_i的倍數中被m_i除餘1的數t_i，則x = r₁t₁ + r₂t₂ +…+ r_nt_n + m₁·m₂·m₃·…·m_n·k，其中k為整數。

比較一下拉格朗日插值多項式的問題：

假設有一個不大於二次的多項式f(x)，被x – 3除餘2，被x – 5除餘3，被x – 7除餘2，試求f(x)。

我們可以用上面解韓信點兵的想法來解這題：考慮不大於二次的多項式f₁(x)，被x – 3除餘1，被x – 5和x – 7整除，則可設f₁(x) = a(x – 5)(x – 7)，由餘式定理知，f₁(3) = 1，所以a = 1/(3 – 5)(3 – 7)。

同理，若不大於二次的多項式f₂(x)，被x – 3整除，被x – 5除餘1，被x – 7整除，則可設f₂(x) = b(x – 3)(x – 7)，由餘式定理知，f₂(5) = 1，所以b = 1/(5 – 3)(5 – 7)。若不大於二次的多項式f₃(x)，被x – 3和x – 5整除，被x – 7除餘1，則可設f₃(x) = c(x – 3)(x – 5)，由餘式定理知，f₃(7) = 1，所以c = 1/(7 – 3)(7 – 5)。

於是，f(x) = 2 f₁(x) + 3 f₂(x) + 2 f₃(x)就是答案了。

所以，我們可以說拉格朗日插值法就是中國剩餘定理的多項式版本。

相關文章：牛頓、拉格朗日多項式插值法與基底變換

一個鴿籠原理的簡單應用：模n的斐波那契數列是循環數列

    好久沒寫部落格文章了，前幾天被幾個學生嫌，她們覺得我「墮落了」，那就寫一篇關於最近在準備數論培訓課程裡用到的一個小小題目和有趣的延伸！

    我們校內的培訓講義裡有一道題：

    求證：對任意整數n，存在n的一個倍數，它是僅由數字2與0組成的。

    要解答這問題並不太難，只要考慮集合{2, 22, 222, 2222, ...}，在mod n的時候，至少會有兩個元素同餘，把這兩個數相減的差，就是由2和0所構成，且會被n整除。

    前幾天跟一個科裡的老師在聊，斐波那契數列(Fibonacci sequence: Fn+1 = Fn + Fn-1，F1 = F2 = 1)在mod n (這裡n > 2)的時候的表現，其中有一個直覺上存在的性質，就它會循環。當然我們這裡定義的循環指的是：存在一個正整數p，使得對於任意正整數i，都滿足Fp+i ≡ Fi (mod n)，而滿足這個同餘式最小的p，稱為斐波那契數列在模n時的最小週期。

    要證明「斐波那契數列在模n時會循環」的這個性質，基本上跟上面這培訓講義裡的題目用的方法差不多：

    數列的遞迴關係已經告訴我們，只要知道數列中相鄰的兩數，就能決定下一數為何，而這相鄰兩數在mod n時頂多只有n²種可能，所以考慮集合{(Fi, Fi+1) ∣ 1 ≦ i ≦ n²+1}的元素，在mod n時，必至少有兩組同餘，即Fi ≡ Fj，Fi+1 ≡ Fj+1 (mod n)，因此Fi+2 ≡ Fj+2 (mod n)，以此類推，可得Fi+3 ≡ Fj+3，Fi+4 ≡ Fj+4，…(mod n)，而且遞迴式也可以逆推回去，得Fi-1 ≡ Fj-1，Fi-2 ≡ Fj-2，…(mod n)，一直推回到斐波那契數列的首項，因此若i < j，則j – i就是其循環週期(但不一定是最小循環週期)。故斐波那契數列在模n時從第一項就開始循環，而且最小循環週期必小於n²。

    其實，上面這個證明，並不只適用在斐波那契數列，用同樣的方法，也可以得到任意的二階遞迴關係式，甚至三階、四階、…遞迴關係式，在模n時都會循環，只是並不能保證是否都是由首項就開始循環。

圓與根軸(課堂筆記)

在坐標平面上給一定點(h, k)(圓心)和一定值r(半徑)，可以決定一圓(x − h)² + (y − k)² = r²，設展開後為x² + y² + dx + ey + f = 0(其中(h, k) = ( −d/2, −e/2), 4r² = d² + e² − 4f)，當然可觀察出若二元二次方程式ax² + bxy + cy² + dx + ey + f = 0，x²項係數和y²項係數相等(a = c≠0)，且xy項係數為0(b = 0)，d² + e² − 4f > 0時，圖形為一圓，d² + e² − 4f = 0時，圖形為一點(h, k)，d² + e² − 4f < 0時無圖形。

因此若圓C₁: x² + y² + d₁x + e₁y + f₁ = 0和圓C₂: x² + y² + d₂x + e₂y + f₂ = 0的線性組合

Γ: k(x² + y² + d₁x + e₁y + f₁) + l(x² + y² + d₂x + e₂y + f₂) = 0

的圖形也會滿足x²項係數和y²項係數相等(= k + l)，xy項係數為0，則Γ的圖形很有機會是一個圓。

若圓C₁和圓C₂有兩個交點A(x₁, y₁)、B(x₂, y₂)，顯然將(x₁, y₁)和(x₂, y₂)代入Γ，無論k和l的值為何，方程式的等號均會成立。所以Γ的圖形必通過A、B兩點，換句話說，若Γ的圖形為一圓，則就是通過A、B兩點的圓，或說是圓心在的中垂線上的圓。這就是「圓系」的概念。

但若是k + l = 0，例如k = 1, l = −1，則Γ: (d₁ − d₂)x + (e₁ − e₂)y + (f₁ − f₂) = 0為一直線，當然也通過A、B兩點，故Γ的圖形為。用另一觀點來看，若點P(x, y)滿足(d₁ − d₂)x + (e₁ − e₂)y + (f₁ − f₂) = 0，即滿足

x² + y² + d₁x + e₁y + f₁ = x² + y² + d₂x + e₂y + f₂

，即

(x − h₁)² + (y − k₁)² − r₁² = (x − h₂)² + (y − k₂)² − r₂²

其中(h₁, k₁)和r₁是圓C₁的圓心和半徑，(h₂, k₂)和r₂是圓C₂的圓心和半徑，而(x − h₁)² + (y − k₁)²就是點P(x, y)到圓C₁的圓心(h₁, k₁)的距離平方，所以(x − h₁)² + (y − k₁)² − r₁²就是點P(x, y)到圓C₁的切線段長的平方。所以上式的意思即表示：Γ為滿足到兩圓的切線段長(的平方)相等的圖形。因為Γ上的點都是滿足方程式(x − h₁)² + (y − k₁)² − r₁² = (x − h₂)² + (y − k₂)² − r₂²的根，所以將Γ稱為圓C₁和圓C₂的「根軸」。

     

有學生問，若點P(x, y)在上，即在兩圓內，就沒有通過P點的切線，那「根軸」又代表什麼意思呢？實際上，若回想國中所學的切割線性質、圓外冪性質、圓內冪性質，可以發現：

若P點在圓外，則，其中D、E分別為點P到圓的最短和最長距離；若P點在圓內，作一以P點為中點的弦，因為

x² + y² + dx + ey + f = (x − h)² + (y − k)² − r² =

因此，也可將Γ上的點視為分別到圓C₁和圓C₂的最短與最長距離的乘積相等的點。

      

(當然我覺得這樣的解釋只是強加一個幾何概念到一個「值」上，實際上它就是滿足一個方程式的點，不過這樣的講法，無論圓C₁和圓C₂是相交於兩點或外切、內切、外離、內離，就都適用了。)

如果兩圓沒有相交，怎麼找出根軸的位置呢？一樣的，從圓外冪性質和切割線性質可知，任作一圓C與兩圓C₁和C₂分別交於A、B和C、D，則和的交點P就會在根軸上。所以如此方式，找出(根軸上的)兩點P₁、P₂，則即為根軸。