中國剩餘定理(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時都會循環，只是並不能保證是否都是由首項就開始循環。