作者winson910343 (小黃)
看板Grad-ProbAsk
標題離散題庫 中國餘數定理
時間Fri Jan 11 14:10:43 2019
不好意思想請教一下
中國餘數定理什麼時候可拆
下面這題如果將x=1 mod 4拆成 x=1 mod 2算出來會跟解答不太一樣
https://i.imgur.com/RMvFYdU.jpg
原本想說是平方數不可拆
但看到中興資工這題
https://i.imgur.com/PHcoS9E.jpg
https://i.imgur.com/wHpnVpv.jpg
他直接將x=7 mod 9 拆成了 x=1 mod 3 算出來結果卻是對的 才有了此疑惑
在麻煩各位大大解說了 感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.204.20.214
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1547187046.A.F5A.html
1F：推 wei12f8158: 解答第一行有提到9、12、21彼此不互質，所以要拆 01/11 14:22
2F：→ wei12f8158: 第一題的4、5、19彼此互質，所以不用拆 01/11 14:23
3F：→ wei12f8158: 不是不用拆，是不能拆XD 01/11 14:24
4F：→ winson910343: 想在問一下 這題筆記上寫mod81 不可拆 可是3跟81不 01/11 14:34
5F：→ winson910343: 互質 照這樣說應該可以拆吧？ 01/11 14:34
7F：推 wei12f8158: 我沒記錯的話要看三個數GCD(3、16、81)=1，所以不可 01/11 14:38
8F：→ wei12f8158: 拆 01/11 14:38
9F：→ winson910343: 那想請教一下這題gcd(2,3,15)等於1卻可拆 01/11 14:51
12F：→ wei12f8158: 下是要兩兩互質，不是GCD(2、3、15）=1，然後那題的81 01/11 15:53
13F：→ wei12f8158: 不能拆是因爲拆出來的數也要是互質才行 01/11 15:53
14F：→ wei12f8158: 不對，我好像又漏了什麼條件，這樣中興那題的9不能拆 01/11 15:56
15F：→ wei12f8158: 成3*3，等其它神人補充好了SORRY TAT 01/11 15:56
16F：→ Ricestone: 中興資工那個9根本不用拆 01/11 15:58
17F：→ Ricestone: 不互質的時候需要做的事情是確認每條都相符 01/11 15:58
18F：→ Ricestone: 12跟21拆開時，得到都是1mod3，跟7mod9相符，所以可做 01/11 15:59
19F：→ Ricestone: 7mod9只有=>1mod3 01/11 16:00
20F：→ wei12f8158: R大請問，高第一的那題81為什麼不能拆呢？ 01/11 16:13
21F：→ Ricestone: 就跟9不應該拆一樣啊 01/11 16:15
22F：→ Ricestone: 1mod3這件事情，在mod9裡面就是有1,4,7這三個東西 01/11 16:15
23F：→ Ricestone: 你要能拆，就是要只有一種可能才能拆 01/11 16:17
24F：→ wei12f8158: 懂了，謝謝R大 01/11 16:21
25F：→ winson910343: 了解了 感謝w大跟R大！！ 01/11 16:59
26F：推 jojoboy0115: 想問為什麼7mod9 等價於1mod3 ? 01/11 18:20
27F：→ Ricestone: 不等價，書上寫錯了 01/11 18:25