ASP 討論版

	昌爸工作坊論壇
\|─	餘數不同，中國剩餘定理，國中學生發問


回覆	搜尋	返回	管理

作者	標題: 餘數不同，中國剩餘定理，國中學生發問
crazyho	發表於: 2017/8/23 下午 06:06:48 麻煩各位老師，題目如下：有一正整數加上5可以被6整除，加上4可以被7整除，加上3可以被8整除，加上2可以被9 整除，則此數最小為多少？謝謝
yani	回覆於: 2017/8/24 上午 02:42:03 以下文字記號(a,b,c,x)皆為整數，x=a(b)表示x-a是b的倍數即x除以b餘a，其中商可為任意整數,餘數a也可任意整數(含負整數),例如7=2=-3=12(5)
yani	回覆於: 2017/8/24 上午 02:42:31 因為6,9不互質,可先不管除數6,先找x=3(7)=5(8)=7(9) 對除數7言,找8,9的倍數,但除以7餘1的數: 89=12(7)=2(7),89(4)=8=1(7), 288=1(7) 對除數8言,找7,9的倍數,但除以8餘1的數: 79=(-1)1(8)=-1(8), -63=1(9) 對除數9言,找7,8的倍數,但除以9餘1的數: 78=(-2)(-1)=2(9),78(-4)=-8=1(9), -224=1(9) x=2883+(-63)5-2247+78*9k=-1019+504k=1(6) 正整數x=-1019+504k=493為最小值
?	回覆於: 2017/8/25 下午 07:44:00
idea	回覆於: 2018/11/27 上午 04:05:02 上5可以被6整除，加上4可以被7整除，加上3可以被8整除，加上2可以被9 觀察題目和皆為11 可知 -11 為其一整數解 6,7,8,9最小公倍數為504 -11+504=493 則為其最小正整數解
克勞棣	回覆於: 2018/12/3 下午 08:27:53 有一正整數加上5可以被6整除，加上4可以被7整除，加上3可以被8整除，加上2可以被9 整除，亦即「該正整數被6除餘1，被7除餘3，被8除餘5，被9除餘7」。用試誤法「被6除餘1」的正整數呈等差數列，首項為1，公差為6，依序是1, 7, 13, 19, 25, 31,.....，其中31被7除餘3；「被6除餘1，被7除餘3」的正整數呈等差數列，首項為31，公差為[6,7]=42，依序是 31, 73, 115, 157,.....，其中157被8除餘5；「被6除餘1，被7除餘3,被8除餘5」的正整數呈等差數列，首項為157，公差為[6,7,8] =168，依序是157, 325, 493,.....，其中493被9除餘7；所以「被6除餘1，被7除餘3,被8除餘5，被9除餘7」的正整數最小的就是493。
克勞棣	回覆於: 2018/12/3 下午 09:46:33 有一正整數被6除餘1，被7除餘3，被8除餘5，被9除餘7，求其最小值。用同餘式預備定理1(乘法):a,b,k為整數，m為正整數，若a≡b (mod m)，則ka≡kb (mod m)。預備定理2(放大縮小模數)：a,b為整數，k,m為正整數，a≡b (mod m)，若且唯若ka≡ kb (mod km)。 n≡1 (mod 6) → 7n≡7 (mod 67) n≡3 (mod 7) → 6n≡18 (mod 76) 兩式相減，(7-6)n≡n≡7-18≡-11 (mod 42) n≡-11 (mod 42) → 4n≡4(-11)≡-44 (mod 168) → 20n≡-220≡-52 (mod 168) n≡5 (mod 8) → 21n≡215≡105≡-63 (mod 168) 兩式相減，(21-20)n≡n≡-63-(-52)≡-11 (mod 168) n≡-11 (mod 168) → 3n≡3(-11)≡-33 (mod 504) → 57n≡19(-33)≡-627≡-123 (mod 504) n≡7 (mod 9) → 56n≡56*7≡392≡-112 (mod 504) 兩式相減，(57-56)n≡n≡-123-(-112)≡-11≡493 (mod 504) 所以最小值是493。 (沒想到用同餘式比用試誤法還繁瑣)