推 alan23273850: 還是 hen 麻煩 R 06/11 01:59
※ 引述《raymond92928 (raymond)》之銘言：
: https://i.imgur.com/cxXQAvz.jpg
: 官方答案應該是不對的
: 如果題目沒有錯的話，有辦法用非暴力解嗎？
事實上這題是可以手算的
而且一直在解 mod 8, mod 9 , mod 7的聯立同餘
欲解
x=1 mod 2^9
x=2 mod 3^6
x=3 mod 7^3
注意到 2^9*3^6*7^3 = (8*9*7)^3
先考慮
x=1 mod 8
x=2 mod 9
x=3 mod 7
容易中國剩餘定理算出, x= -63 + 56 + 72*5 mod 8*9*7
=353 mod 504
在考慮
x=1 mod 8^2
x=2 mod 9^2
x=3 mod 7^2
設 x= 353 + 504k
則 1= 353 + 504k mod 64
-352 = 504k mod 64
-44 = 63k mod 8
即 k = 4 mod 8
同理, 可知
k=3 mod 9
k=3 mod 7
因此, k=-4*63 -3*56 + 72*5 mod 504
= -60 mod 504
故 x= 353+ 504*(-60) mod 504^2
設 x=353+ 504*(-60) + 504^2*k
則 1 = 353+ 504*(-60) + 504^2*k mod 8^3
29888 = 504^2*k mod 8^3
467 = 63^2*k mod 8
k = 3 mod 8
同理
29889 = 504^2*k mod 9^3
369 = 56^2*k mod 9
k = 0 mod 9
29890 = 504^2*k mod 7^3
610 = 72^2*k mod 7
1 = 4k mod 7 ===> k=2 mod 7
而 k=3 mod 8
k=0 mod 9
k=2 mod 7
的解為 k=-3*63 + 0 + 72 mod 504
= -117 md 504
所以最後, x=353+ 504*(-60) + 504^2*(-117) mod 504^3
=98274305 mod 504^3
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.34.159
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1528650925.A.589.html