斐波那契 (Fibonacci) 《算經(Liber Abaci)》(1202) 裏的一條題目 Fibonacci

yy2admin

解以下同餘式組

x=2 (mod 3) = 3 (mod 5) = 4 (mod 7)

即是
某整數 x 被 3 除餘 2, 被 5 除餘 3, 被 7 除餘 4, 求 整數 x.

此題目與《孫子算經》的"物不知數"題有點類似.

yy2admin

中國最初在《孫子算經》介紹“物不知數”的解法, 並寫出以下的歌訣:
“三人同行七十稀，
五樹梅花廿一枝。
七子團圓正半月，
除百零五便得知。”

後來南宋秦九韶在他的《數書九章》(13世紀) 提出了一個更廣泛的解法“大衍求一術”, 而西方要到19世紀高斯才找出和中國完全一致的解法。從此，此解法正式被稱為“中國剩餘定理”。

yy2admin

三人同行七十稀，      -->  被 3 除餘 2,  取 70 乘 餘數 2 得 140  
五樹梅花廿一枝。      -->  被 5 除餘 3,  取 21 乘 餘數 3 得 63
七子團圓正半月，      -->  被 7 除餘 4,  取 15 乘 餘數 4 得 60
除百零五便得知。”  -->  把以上總和不斷減 105, 直至餘數少於 105 便是答案
                                               即 140 + 63 + 60 = 263
                                   263 - 105 x 2 = 263 - 210 = 53
                                   故此未知數 x 是 53.

yy2admin

那麼 70, 21, 15 是怎麼來的?
例如 3,5,7,
計算 定數 3, 即要一個數既是 5 和 7的公倍數, 但被 3 除卻要餘 1,
       5 和 7的公倍數是 35(衍數), 35 被 3 除餘 2, 不餘1; 下一個公倍數是 70,
       70 被 3 除餘 1, 故此 除 3 ,  取 70.
       3 和 7的公倍數是 21, 21 被 5 除餘 1, 故此 除 5 ,  取 21.
       3 和 5的公倍數是 15, 15 被 7 除餘 1, 故此 除 7 ,  取 15.

Michelle

好像很難也...--