中國餘數定理（Chinese remainder theorem）

有個古老謎題：某數除以 3 餘 2、除以 5 餘 3、除以 7 餘 2——它是多少？中國餘數定理（Chinese remainder theorem）說，只要那些除數彼此沒有共同因數，這樣的數一定存在，且一旦固定範圍就唯一。直覺上，知道一個數對好幾個互質除數的餘數，就能在一個完整週期內把它精確地釘住，就像同時知道星期幾、幾號、幾月，就能在一年內定出唯一一天。

精確地說：若 m1, m2, ..., mk 兩兩互質（任兩個 gcd 為 1）且 M = m1*m2*...*mk，則同餘系統 x = a1 mod m1、x = a2 mod m2、…、x = ak mod mk 在 0..M-1 範圍內恰有一個解 x。對兩個同餘式 x = a1 mod m1 與 x = a2 mod m2 的構造，令 Mi 為其餘模數的乘積：x = a1*M1*(M1^(-1) mod m1) + a2*M2*(M2^(-1) mod m2)，全部對 M 取模，其中每個反元素由擴展歐幾里得演算法取得。這構造之所以成立，是因為每一項被設計成對自己的 mi 等於 ai、對其他模數等於 0，於是總和同時對每個模數有正確的餘數。以 m=3,5,7、M=105 追蹤該謎題：求解得 x = 23，確實 23 = 2 mod 3、23 = 3 mod 5、23 = 2 mod 7。

中國餘數定理既是計數工具，也是計算加速器。它告訴你：對一個大合數 M 取模運算，等價於對每個互質因數獨立取模運算，這讓演算法能把一個難算的大數計算拆成幾個小的、可平行的計算，再把答案黏回去。這個技巧加速了 RSA 解密（分別對兩個質因數 p 與 q 取模計算，再重組）、大整數算術，以及許多競賽題。唯一不能省的要求是兩兩互質：若兩個模數共用因數，系統可能無解或多解，乾淨的一一對應就崩潰了。