中國剩餘定理一問

這個情況不能用中國剩餘定理來計
以下系一個能用中國剩餘定理的例子：http://hk.knowledge.yahoo.com/question/question?qid=7010072101787
------------------------------------------------------------------------------------------------------------------
問：a / 3 餘 2
a / 5 餘 3
a / 8 餘 6
求 a 的最小值
解：
首先分別計出3*5的幾多倍會被8除左之後餘1..然後攞個數值出來
再計出3*8的幾多倍會被5除左之後餘1..然後攞個數值出來
再計出5*8的幾多倍會被3除左之後餘1..然後攞個數值出來
呢3個數值分別系105,96,40
然後把105*6+96*3+40*2=998
然後把998-120 (120系3,5,8的最小公倍數)
=878
再-120,一直減到個數細過120果個就系a的最小值
即38
其實如果單純計a的值會有無限個解=38+120n
n可以代任何正整數和0
-----------------------------------------------------------------------------------------------------------------
以上可以用的例子中看出,3與5是互質的,而3與8也是互質的,5與8都是互質的
但你的問題中,6與9不是互質的,他們是可以被3除盡
----------------------------------------------------------------------------------------------------------------
互質可能理解成2者的最大公因數是1,這2個數就稱為互質
----------------------------------------------------------------------------------------------------------------
為什麼這些數要互質才能用中國剩餘定理計算呢?
若我地試下用中國剩餘定理計第一步：
首先分別計出6*7的幾多倍的數會被9除左之後餘1
可以用一個方程表示：6*7n=9a+1
即其中n和a必為一整數
把這一方程進一步化簡,可得
42n-9a=1
3(14n-3a)=1
由於n與a都是一整數,14n-3a都一定系整數
呢條式可以咁理解：
3乘以一整數等於1
但大家都知3乘任何一個整數都不可能會等於1
所以這方程必定不存在整數解
----------------------------------------------------------------------------------------------------------------
所以中國剩餘定理的第一步都做唔到,之後果d步驟都唔可能做到
----------------------------------------------------------------------------------------------------------------
而且以上問題根本不存在解
因為以上問題可以化成3個方程去理解：
x為解,b,c,d為商
x=6b+1
x=7c+5
x=9d+2
其中b,c,d,x應為整數
因為除數的商一定要系整數
如果把x=6b+1代入x=9d+2
可得
6b+1=9d+2
6b-9d=1
3(2b-3d)=1
由於b,d為整數,2b-3d都一定系整數
上式可理解成3乘一個整數等於1,但我們都知3乘任何一個整都不可能等於1
所以b,d不存在整數解
所以一定沒有一個數能同時被6除餘1和被9除餘2
-----------------------------------------------------------------------------------------------------------------
以上問題沒有一個解,中國剩餘定理當然計不到.,我相信如果有其他方法計這一類數,但都一定不能計出這問題的解,"因為這問題不存在整數解"

Chinese remainder threorem requires the pairwise coprime, therefore for every pair of number we must have their GCD = 1. In this problem, the GCD(6, 9) = 3 =/= 1. Therefore the Chinese remainder theorem does not apply.

In this particular example, the solution does not exists. We can see the answer must be 6a + 1 (with a being an integer), therefore it must be 3b + 1 (with b = 2a being an integer).

But the answer must also be 9c + 2 (with c being an integer), therefore it must be 3d + 2 (with d = 3c being an integer), this contradicts with the above and therefore a solution cannot exist.