孫子定理與線性同餘方程組

我國在公元四世紀左右寫成的《孫子算經》中的「物不知數問題」便是一線性同餘方程組 (System of Linear Congruence Equations) 的問題。

例:今有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二,問物幾何?

這相當於解 x = 2 (mod 3)、x = 3 (mod 5) 及 x = 2 (mod 7) 的方程組。

 

在 1593 年程大位在《算法統宗》一書中將這個問題的解法總結成一口訣:

「三人同行七十稀,五樹梅花廿一枝,七子團圓半個月,除百零五便得知。」

意思是說我們把 2, 3 和 2 分別乘上 70, 21 和 15 (半月即 15 日),再加起來,求 105 除以該總和的餘數便是答案。即 2*70 + 3*21 + 2*15 = 233,即答案為 233-2*105 = 23。但是當中的 70, 21, 15 或 105 是如何計出來,我們便得看看孫子定理 (Sun Zi Theorem) 或孫子剩餘定理 (Sun Zi Remainder Theorem) 或中國剩餘定理 (Chinese Remainder Theorem)。

 

我們設 m1, m2, m3, ...... mn 是 n 個兩兩互素的正整數,而有一正整數 N 使

N = ai (mod mi) 對於所有 i = 1 至 n

而孫子定理告訴我們這是有解的且在模 M 下,M 為所有 mi 的乘積。

解法是這樣的,我們得找尋 di,使 di = 1 (mod mi),但 di = 0 (mod mj) ,其中 i 和 j 是 1 至 n 兩個不同的整數。

而解便是 a1d1 + a2d2 + ...... + andn 在所有模 M 下的最小非負剩餘類 (Least Non-negative Residue Class)中的數。

 

原因不難理解,所有 ajdj = 0 (mod mi) 當 i 不等於 j 時。因而解式中只有 aidi 不為零,故乎合問題要求。而因為 m1, m2, m3, ...... mn 是 n 個兩兩互素的正整數,所以最後我們可以把同餘 (Congruence) 的性質,得到解。關於同餘的性質,可參看《同一餘數的學問》一文。

 

例:解 x = 1 (mod 3), x = 2 (mod 5), x = -3 (mod 7) 及 x = 4 (mod 8) 的所有整數解。

解:5, 7, 8 的最小公倍數 (Least Common Multiple, L.C.M.) 即 5*7*8 = (-1)*1*(-1) = 1(mod 3),所以我們用這 L.C.M. 作為乘數便可以,即 280。再計 3, 7, 8 的 L.C.M. 得 3*7*8 = (-2)*2*(-2) =(-2) (mod 5),即我們要把 L.C.M. 乘以 2 才可合用,故取 2*3*7*8 = 336,又計 3, 5, 8 的 L.C.M. 得 3*5*8 = 3*(-2)*1 = 1 (mod 7),故這 L.C.M. 合用,即取 3*5*8 = 120,再計 3*5*7 = 3*(-3)*(-1) = 1 (mod 8),這亦合用,取 3*5*7 = 105。另 M = 3*5*7*8 = 840。

因而得解 = 280*1 + 336*2 + 120*(-3) + 105*4 = 652 ,因為 652 少於 840 ,所以 652 + 840t,t 取任意整數。

 

當然同餘的問題何止線性,同餘的世界和別的代數方程世界一樣,也有二次方程、三次方程、高次方程、多元方程等,這正是等著有心之人去開拓的新世界。