用中國剩餘定理解一題整數除法問題(15點)

Question

某正整數除以5餘3，除以6餘1，除以14餘5，求某正整數最小是多少？用中國剩餘定理解(不用此定理不給點)想好久，解不出來肯定有答案，因為是自己出題目考自己。

Answer 1

由題可知
該數除以 2餘 1, 除以 3 餘 1, 除以 5餘 3, 除以 7餘 5
令特解 = 3*5*7*a + 2*5*7*b + 2*3*7*c + 2*3*5*d
得到
mod(3*5*7*a, 2) = 1 (因為其他三項會整除)
mod(2*5*7*b, 3) = 1
mod(2*3*7*c, 5) = 3
mod(2*3*5*d, 7) = 5
=>
mod(1*1*1*a, 2) = 1
mod[(-1)*(-1)*1*b, 3] = 1
mod[2*(-2)*2*c, 5) = 3
mod[2*3*(-2)*d, 7] = 5
=>
mod(a, 2) = 1
mod(b, 3) = 1
mod(-8c, 5) = 3
mod(-12d, 7) = 5
=>
a = 1, b = 1, c = -1, d = -1

特解
= 3*5*7*a + 2*5*7*b + 2*3*7*c + 2*3*5*d
= 3*5*7*1 + 2*5*7*1 - 2*3*7*1 - 2*3*5*1
= 103

又, 最小公倍數(2, 3, 5, 7) = 210
所以通解 = 103 + 210n, n為自然數

Answer 2

x ＝ 3*5*7*a ＋ 2*5*7*b ＋ 2*3*7*c ＋ 2*3*5*d

1) 3*5*7*a ＝ 1 (mod 2)
a ＝ 1 (mod 2)
a ＝ 1

2) 2*5*7*b ＝ 1 (mod 3)
b ＝ 1 (mod 3)
b ＝ 1

3) 2*3*7*c ＝ 3 (mod 5)
-3*c ＝ 3 (mod 5)
c ＝ -1

4) 2*3*5*d ＝ 5 (mod 7)
-5d ＝ 5 (mod 7)
d ＝ -1

x ＝ 3*5*7*1 ＋ 2*5*7*1 ＋ 2*3*7*(-1) ＋ 2*3*5*(-1) ＝ 103

Answer 3

設某正整數為5a+3
以第1和2的條件可列出：5a+3=6b+1
移項後為：5a+2=6b
5a+2同餘0(mod6)
a的最小值為2
由第1和2個條件求出某正整數為30n(5和6的最小公倍數)+13
最再加入第3個條件為：除以14餘5
因此，可以列出式子：30n+13=14m+5
移項後為：30n+8=14m
2n+8同餘0(mod14)
n的最小值為3
由以上算式可知：某正整數的最小值為30*3+13=103
答：103

Answer 4

p取0才是最小的

Answer 5

利用餘式定理裡的階梯假設法
設符合題意的數為 X
X=﹝5，6，14﹞p+﹝5，6﹞q+5r+3 → r取8最小
=210p+30q+43 → q取2最小
=210p+103 → p取1最小
=313

2006-02-14 21:42:46 補充：
P是取0才對...答案是103抱歉