鬼谷算題

有看過<<射雕英雄傳>>都會記得黃蓉考瑛姑呢條 "鬼谷算題" :

"今有物不知其數,三三數之賸二,五五數之賸三,

七七數之賸二,問物幾何? "

化作現代的數學語言是 :

"有整數x,x÷3餘2; x÷5餘3; x÷7餘2,求x 。"

瑛姑想了許久,只試出 x = 23 是其中一個解,但除此之外,有沒有數仍可作為x?

這道題是一個不定方程問題,在數論 (Number Theory)中屬於一次同餘問題。<<孫子算經>>給出了它的一般解法, 有人把它編成歌訣 :

" 三人同行七十稀五樹梅花廿一枝

七子團圓月正半除百零五便得知"

寫成公式就是 :

"x=70r1+21r2+15r3-105 n,其中n為任意整數,而r1,r2,r3分別為各次的餘數。"

如把r1=2,r2=3,r3=2代入,並取n=2,求得x=23,這是鬼谷題的最小正整數解。<<孫子算經>>的作者是怎樣得到這公式呢?

觀察一

如果 x1x2 都是解那麼 x1 - x2 必是 105 的倍數

因為 x1 x2 = (x1 r1) ( x2 r1) = ( 3 的倍數 ) ( 3 的倍數 ) = 3 的倍數,同理,x1 x2 都是 5 和 7 的倍數,而 3, 5, 7 的最小公倍數是 105,因此有觀察一。

由此得知,x2 = x1 105 n,其中 n 為某整數。因此通解公式必是形如

x = x1 105 n,其中 n 為任意整數。

因此如能一般地(不論 r1,r2,r3 是多少)找得一個特別解 x1,便能找到通解公式了。

觀察二

r1 作為 x 除 3 後的餘數,當然有 r1 ÷ 3 餘 r1,但

2r1÷3,3r1÷3,4r1÷3,...等的餘數是多少?答案仍舊是 r1 的有 4r1÷3,7r1÷3,10r1÷3,...

(當然啦! 因為 (3 m +1) r1 = 3 m r1+ r1 )

特別是 70 r1÷3 餘 r1 (注意 : 70 不但等於 3×13 + 1,而且還是 5 和 7 的公倍數)。

同樣地,21 r2÷5 餘 r2,15 r3÷7 餘 r3

因此x1 = 70 r1 + 21 r2 + 15 r3 滿足條件是一個特別解

由觀察一及觀察二所得, 便有鬼谷題的通解了。

以下是鬼谷題的推廣:

中國餘式定理

x÷m1 餘 r1 ; x÷m2 餘 r2 ; x÷m3 餘 r3 ; ... ; x÷mk 餘 rk

如果 m1,m2,m3 , ...,mk 除1外沒有公因子,這樣 x 必定有解,且通解公式為

x = x1 (m1m2m3...mk) n,其中 n 為任意整數, x1是一個特別解 。