標籤: mathematics

這是個古老的數學問題, 當然也有對應的解法. 在解這個數學問題之前, 我們先來看簡單一點的題目, 就是相同餘數的數字.

舉例來說, 某數除以 7 餘 4, 除以 13 也餘 4, 則某餘最小的自然數為何?

計算方式還蠻單純的, 就是 7 和 13 的最小公倍數, 再加上 4 即得, 如下:

lcm(7,13) = 91, 由於兩數互質, 所以最小公倍數就是該兩數的乘積, 故答案則為 91 + 4 = 95

另一個變形的題目, 某數除以 7 餘 5, 除以 13 餘 11, 除以 15 餘 13, 則某數的最小自然數為何?

再看一下題目, 雖然和上面的同餘數不太一樣, 不過有個規律, 就是都差 2 就會整除, 也就是雖然餘數不一樣, 但同樣少了 2, 所以計算方式也很類似, 找出 7, 13, 15 的最小公倍數, 然後減 2就是答案了, 如下:

lcm(7, 13, 15) = 1365, 故答案為 1365 – 2 = 1363

以上兩種都是比較單純的餘數問題, 再來看看這個中國餘數定理的問題:

孫子算經中的: 有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二。問物幾何？

換成數學白話, 某數除以 3餘 2, 除以 5餘 3, 除以 7餘 2, 某數為何?

這個既不是同樣的餘數, 也不是同樣的差某一值可整除, 要如何解呢? 這時會用到一些餘數的式子, 可以先參考這裡: http://www.mikekong.net/Maths/Problems/chinese_remainder02.html

所以只需要先找出 5, 7 的公倍數, 除以 3餘 1的; 再找出 3, 7的公倍數, 除以 5餘 1的; 再找出 3, 5的公倍數, 除以 7餘 1的, 如下:

找出 5, 7 的公倍數, 除以 3餘 1的: 5 x 7 x 2 = 70, 該數除以 3會餘 1
找出 3, 7的公倍數, 除以 5餘 1的: 3 x 7 = 21, 該數除以 5會餘 1
找出 3, 5的公倍數, 除以 7餘 1的: 3 x 5 = 15, 該數除以 7會餘 1

然後利用:
a ≡ b (mod m) 則 ac ≡ bc (mod m) 這個式子(注意反之不然), 得
70 ≡ 1 (mod 3) … (a)
21 ≡ 1 (mod 5) … (b)
15 ≡ 1 (mod 7) … (c)
因為要除以 3餘 2, 所以 (a) x 2:
70 x 2 ≡ 1 x 2 (mod 3) … (d)
因為要除以 5餘 3, 所以 (b) x 3:
21 x 3 ≡ 1 x 3 (mod 5) … (e)
因為要除以 7餘 2, 所以 (c) x 2:
15 x 2 ≡ 1 x 2 (mod 7) … (f)

再利用:
a ≡ b (mod m) 則 a + c ≡ (b + c) (mode m) 這個式子,
並綜合以上 (d), (e), (f) 得該數應為
x ≡ (70 x 2 + 21 x3 + 15 x 2)(mod 105)

所以最小的某數應為 23, (即 70×2 + 21×3 + 15×2 – 105×2 = 23)

相關閱讀:
http://zh.wikipedia.org/wiki/%E4%B8%AD%E5%9B%BD%E4%BD%99%E6%95%B0%E5%AE%9A%E7%90%86
http://www.mikekong.net/Maths/Problems/chinese_remainder02.html
http://www.geocities.ws/goodprimes/SCCongruence.html