[Math] 中國餘數定理

《孫子算經》的下卷第26題：「今有物不知其數，三三數之剩二；五五數之剩三；七七數之剩二。問物幾何？」
翻成白話文：
x為一整數且x º 2 mod 3，x º 3 mod 5，x º 2 mod 7，求 x 等於多少？
令 n₁ = 3, n₂ = 5, n₃ = 7 ;
令 n = n₁ n₂ n₃ = 105 ;
令 r₁ = 2, r₂ = 3, r₃ = 2;
令 N₁ = n/n₁ = 35, N₂ = n/n₂ = 21, N₃ =n/n₃ = 15;
若 M₁N₁ º 1 mod n₁，則 M₁ = 2
若 M₂N₂ º 1 mod n₂，則 M₂ = 1
若 M₃N₃ º 1 mod n₃，則 M₃ = 1
因此 x = (r₁M₁N₁ + r₂M₂N₂ + r₃M₃N₃) mod n
x = (2*-1*35 + 3*1*21 + 2*1*15 ) mod 105
x = 23

《孫子算經》作者及年代不詳，推測約在西元4、5百年左右。
中國餘數定理在計算機科學中應用相當多，尤其是密碼學及資料壓縮。
是混資訊界的人不得不懂的數學基本知識。

本篇文章由 glCheng's Blog 轉錄，特此感謝。