離散題庫 中國餘數定理

[winson910343 (小黃)]

不好意思想請教一下
中國餘數定理什麼時候可拆

下面這題如果將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://www.ptt.cc/bbs/Grad-ProbAsk/M.1547187046.A.F5A.html
推 wei12f8158: 解答第一行有提到9、12、21彼此不互質，所以要拆
→ wei12f8158: 第一題的4、5、19彼此互質，所以不用拆
→ wei12f8158: 不是不用拆，是不能拆XD
→ winson910343: 想在問一下 這題筆記上寫mod81 不可拆 可是3跟81不
→ winson910343: 互質 照這樣說應該可以拆吧？
→ winson910343:  https://i.imgur.com/NAbxogq.jpg
推 wei12f8158: 我沒記錯的話要看三個數GCD(3、16、81)=1，所以不可
→ wei12f8158: 拆
→ winson910343: 那想請教一下這題gcd(2,3,15)等於1卻可拆
→ winson910343:  https://i.imgur.com/gCo7sAW.jpg
推 wei12f8158:  https://i.imgur.com/T3tiYQp.jpg 想起來了，更正一
→ wei12f8158: 下是要兩兩互質，不是GCD(2、3、15）=1，然後那題的81
→ wei12f8158: 不能拆是因爲拆出來的數也要是互質才行
→ wei12f8158: 不對，我好像又漏了什麼條件，這樣中興那題的9不能拆
→ wei12f8158: 成3*3，等其它神人補充好了SORRY  TAT
→ Ricestone: 中興資工那個9根本不用拆
→ Ricestone: 不互質的時候需要做的事情是確認每條都相符
→ Ricestone: 12跟21拆開時，得到都是1mod3，跟7mod9相符，所以可做
→ Ricestone: 7mod9只有=>1mod3
→ wei12f8158: R大請問，高第一的那題81為什麼不能拆呢？
→ Ricestone: 就跟9不應該拆一樣啊
→ Ricestone: 1mod3這件事情，在mod9裡面就是有1,4,7這三個東西
→ Ricestone: 你要能拆，就是要只有一種可能才能拆
→ wei12f8158: 懂了，謝謝R大
→ winson910343: 了解了 感謝w大跟R大！！
推 jojoboy0115: 想問為什麼7mod9 等價於1mod3  ?
→ Ricestone: 不等價，書上寫錯了