關於中國剩餘定理題目的自創解法(10點)

Question

我不是要解答，我是要意見和評論，謝謝！請問這樣算可以嗎？正整數x除以3餘1，除以5餘4，除以7餘2，除以11餘5，求x的最小值x≡1(mod 3)→乘以35→35x≡35(mod 105)---(1)x≡4(mod 5)→乘以21→21x≡84(mod 105)---(2)x≡2(mod 7)→乘以15→15x≡30(mod 105)---(3)x≡5(mod 11)→乘以105→105x≡525(mod 1155)---(4)(1)式+(2)式+(3)式71x≡149≡44(mod 105)→乘以11→781x≡484(mod 1155)---(5)令781a+105b=1用Euler法求整數解781a-1≡0(mod 105)→46a-1≡0(mod 105)，令46a-1=105c105c+1≡0(mod 46)→13c+1≡(mod 46)，令13c+1=46d46d-1≡0(mod 13)→7d-1≡0(mod 13)，令7d-1=13e13e+1≡0(mod 7)→-e+1≡0(mod 7)取e=1→d=2→c=7→a=16→b=-119所以(4)式*(-119)+(5)式*16x≡525*(-119)+484*16≡-54731≡709(mod 1155)所以x最小值709--------嗚！嗚！我不想當分隔線-------105x≡525(mod 1155)---(4)781x≡484(mod 1155)---(5)還有另外一個方法可解出x(5)式-(4)式*746x≡-3191≡-3191+31*1155≡32614(mod 1155)除以46，x≡709(mod 1155)這是偷懶用Excel求得31的按部就班還是可以用Euler法令46x=-3191+1155a1155a-3191≡0(mod 46)→5a+29≡0(mod 46)，令5a+29=46b46b-29≡0(mod 5)→b-4≡(mod 5)取b=4→a=31

Answer 1

您的解法沒錯，但是太煩了，建議使用下列方法，學生比較容易理解
[解法一] 韓信點兵，雖然麻煩點，但卻可推廣到Lagrange插值法
[解法二] 長除法[除法原理] ，很容易理解
以上兩點提供您參考
[解法一]
韓信點兵：
1. (1)先找一個3，5，7的倍數但是被11除餘5的數，例如 1050
(2)再找一個3，5，11的倍數但是被7除餘2的數，例如 660
(3)再找一個3，7，11的倍數但是被5除餘4的數，例如 924
(4)再找一個5，7，11的倍數但是被3除餘1的數，例如 385
將這4個數相加1050 + 660 + 924 + 385 = 3019
如果比最小公倍數大，減去最小公倍數3019 – 2310 = 709即為所求

[解法二]
長除法[除法原理]
設 n = 11 a + 5
令 a = 7 b + c
∴ n = 11 (7 b + c) + 5 = 7 (11b+c)+4c+5
取 c = 1
∴ n = 77 b + 16
令 b = 5 d + e
∴ n = 77 (5 d + e) + 16 = 5 (77d+15e+3)+2e+1
取 e = 4
∴ n = 385d + 324
令 d = 3 f + g
∴ n = 385 (3 f + g) + 324 = 3 (385f+128g+108)+g
取 g = 1
∴ n = 1155 f + 709

Answer 2

學生？
什麼學生？