[理工] 103中興-中國餘數定理

看板Grad-ProbAsk作者 (joy7658x348)時間9年前 (2017/01/30 16:31), 編輯推噓11(11推 0噓 43→)
留言54則, 7人參與, 最新討論串1/1
http://i.imgur.com/U1tNvaw.jpg
想請問(vi)的中國餘數定理應該怎麼算？ 中興答案給16+84k,k屬於整數 可是當k=1時，x=100(mod9)不會是7啊！ 我自己算是 n1=3, r1=1, N1=28, M1=1 n2=4, r2=0, N2=21, M2=1 n3=7, r3=2, N3=12, M3=5 n=84 所以28+0+120=148=64(mod84) 所以64+84k可是也錯了…… 有沒有版友能夠算ㄧ次 萬分感謝！ 另外(v)的prefix完全不能算 應該是postfix吧？算出來的確是４ 那如果遇到這種題目出錯的 各位當下在考試會寫自己改題目後的答案(如果會算的話) 還是直接跳過空著？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.166.132.162 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485765060.A.88F.html
→
01/30 16:35, , 1F
空著絕對沒分數，自動更正題目吧XD
01/30 16:35, 1F
→
01/30 16:40, , 2F
M3應該是3？
01/30 16:40, 2F
→
01/30 16:49, , 3F
對!原來是錯在M3，謝y大。可是這樣當k=1時，x=100還
01/30 16:49, 3F
→
01/30 16:49, , 4F
是無法mod9餘７啊…另外兩個都可以 那這樣是…？
01/30 16:49, 4F
推
01/30 16:49, , 5F
n2應該拆成質數2？
01/30 16:49, 5F
推
01/30 16:50, , 6F
我算252k+268，三個都驗證過了
01/30 16:50, 6F
→
01/30 16:51, , 7F
問題在於x=7(mod 9)不可以拆
01/30 16:51, 7F
→
01/30 16:53, , 8F
解釋一下，x=4(mod 12)可拆成x=1(mod 3)和x=0(mod 4)
01/30 16:53, 8F
→
01/30 16:54, , 9F
但是x=7(mod 9) imply x=1(mod 3)所以x=1(mod 3)可以
01/30 16:54, 9F
→
01/30 16:55, , 10F
砍掉，同理x=16(mod 21)可拆成x=1(mod 3)和x=2(mod 7)
01/30 16:55, 10F
→
01/30 16:55, , 11F
x=1(mod 3)也可以砍掉，剩下三個下去做就會做出我算的
01/30 16:55, 11F
→
01/30 16:55, , 12F
那個答案
01/30 16:55, 12F
→
01/30 16:56, , 13F
x=7(mod 9)拆掉就會得到中興給的那個答案，但那個答案
01/30 16:56, 13F
→
01/30 16:56, , 14F
很明顯是錯的，就如你驗證的一樣，遇到這種情形我也不
01/30 16:56, 14F
→
01/30 16:56, , 15F
知道該怎麼辦...
01/30 16:56, 15F
推
01/30 16:57, , 16F
x=0 (mod 4)不能拆成 x=0 (mod 2)嗎
01/30 16:57, 16F
→
01/30 16:58, , 17F
x=7(mod 9) => x=1(mod 3)，但反向是不對的，舉例來說
01/30 16:58, 17F
→
01/30 16:59, , 18F
取x=4，4=1(mod 3)但4=\=7(mod 9)
01/30 16:59, 18F
→
01/30 17:00, , 19F
To n大，當然可以喔，可是r=0之後在算rMN的時候就沒差
01/30 17:00, 19F
→
01/30 17:00, , 20F
了，
01/30 17:00, 20F
→
01/30 17:01, , 21F
ㄟ不對，不可以拉，理由就是我剛剛講的XD
01/30 17:01, 21F
→
01/30 17:01, , 22F
平方數不可以直接拆
01/30 17:01, 22F
推
01/30 17:02, , 23F
可是餘數是0會影響嗎@@
01/30 17:02, 23F
→
01/30 17:03, , 24F
印象中n1,n2,n3,...互質就可以，不一定要是質數
01/30 17:03, 24F
→
01/30 17:05, , 25F
這題不會影響，但是他們並不是等價的，其他題就會有影
01/30 17:05, 25F
推
01/30 17:05, , 26F
原來如此 感謝
01/30 17:05, 26F
→
01/30 17:05, , 27F
響，所以這題也不要拆，怕其他題會做錯
01/30 17:05, 27F
推
01/30 17:08, , 28F
那有沒有什麼方式可以判斷不可拆，本來以為是不可拆成互
01/30 17:08, 28F
→
01/30 17:08, , 29F
質兩數才不可拆，這樣好像又多了一個條件(平方之餘不可
01/30 17:08, 29F
→
01/30 17:08, , 30F
拆?)
01/30 17:08, 30F
推
01/30 17:10, , 31F
好像是要拆成互質的兩個數，平方數拆的話，9=3*3，3跟3
01/30 17:10, 31F
→
01/30 17:11, , 32F
就沒互質了，應該沒多條件，安心安心
01/30 17:11, 32F
推
01/30 17:14, , 33F
對耶！感謝y大
01/30 17:14, 33F
→
01/30 17:14, , 34F
這時候再多條件我就要崩潰了QQ
01/30 17:14, 34F
→
01/30 17:15, , 35F
我算出來了，的確同y大說的，不要拆掉就好。答案錯了
01/30 17:15, 35F
→
01/30 17:15, , 36F
。
01/30 17:15, 36F
→
01/30 17:15, , 37F
01/30 17:15, 37F
→
01/30 17:16, , 38F
只要n互質就可以了，應該是重根的不能拆。謝謝兩位！
01/30 17:16, 38F
→
01/30 17:16, , 39F
！
01/30 17:16, 39F
→
01/30 20:42, , 40F
不用互質也可以拆吧 x=3(mod 8) => x=3+8k 拿x去除2,4取
01/30 20:42, 40F
→
01/30 20:42, , 41F
餘數就可以得 x=1(mod 2) 跟 x=3(mod 4) 如果你們是在討
01/30 20:42, 41F
→
01/30 20:42, , 42F
論中國餘數的公式要互質的話就請忽略我說的～
01/30 20:42, 42F
→
01/30 20:46, , 43F
取x=7，則x=1(mod 2)且x=3(mod 4)但x=3(mod 8)不成立
01/30 20:46, 43F
→
01/30 20:47, , 44F
x=3(mod 8) imply x=1(mod 2) and x=3(mod 4)，但
01/30 20:47, 44F
→
01/30 20:47, , 45F
仔細看完留言 請忽略我的回文-.-
01/30 20:47, 45F
→
01/30 20:48, , 46F
x=1(mod 2) and x=3(mod 4) 不保證x=3(mod 8)，因此不
01/30 20:48, 46F
→
01/30 20:49, , 47F
為等價，如果可以拆是指單向成立的話，那的確是可以拆
01/30 20:49, 47F
推
01/30 22:12, , 48F
01/30 22:12, 48F
→
01/30 22:12, , 49F
我不確定是不是正確的作答過程
01/30 22:12, 49F
推
01/31 15:37, , 50F
回ck960785大 你圖中的就跟原po文中的一樣 在k等於1的
01/31 15:37, 50F
→
01/31 15:37, , 51F
時候x會等於100去mod 9就錯了 應該像yupog2003大所講
01/31 15:37, 51F
→
01/31 15:37, , 52F
的9不能拆
01/31 15:37, 52F
→
01/31 23:37, , 53F
16+252k
01/31 23:37, 53F
推
02/01 10:27, , 54F
喔喔對耶！竟然忘記268=252+16可以將252併到k裡面去了
02/01 10:27, 54F
‣ 更多 joy7658x348 的文章
文章代碼(AID): #1OZld4YF (Grad-ProbAsk)