中國剩餘定理(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)就是答案了。

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

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