離散題庫 中國餘數定理

看板Grad-ProbAsk作者 (小黃)時間7年前 (2019/01/11 14:10), 編輯推噓4(4推 0噓 23→)
留言27則, 4人參與, 7年前最新討論串1/1
不好意思想請教一下 中國餘數定理什麼時候可拆 下面這題如果將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
推
01/11 14:22, 7年前 , 1F
解答第一行有提到9、12、21彼此不互質，所以要拆
01/11 14:22, 1F
→
01/11 14:23, 7年前 , 2F
第一題的4、5、19彼此互質，所以不用拆
01/11 14:23, 2F
→
01/11 14:24, 7年前 , 3F
不是不用拆，是不能拆XD
01/11 14:24, 3F
→
01/11 14:34, 7年前 , 4F
想在問一下 這題筆記上寫mod81 不可拆 可是3跟81不
01/11 14:34, 4F
→
01/11 14:34, 7年前 , 5F
互質 照這樣說應該可以拆吧？
01/11 14:34, 5F
→
01/11 14:34, 7年前 , 6F
01/11 14:34, 6F
推
01/11 14:38, 7年前 , 7F
我沒記錯的話要看三個數GCD(3、16、81)=1，所以不可
01/11 14:38, 7F
→
01/11 14:38, 7年前 , 8F
拆
01/11 14:38, 8F
→
01/11 14:51, 7年前 , 9F
那想請教一下這題gcd(2,3,15)等於1卻可拆
01/11 14:51, 9F
→
01/11 14:51, 7年前 , 10F
01/11 14:51, 10F
推
01/11 15:53, 7年前 , 11F
想起來了，更正一
01/11 15:53, 11F
→
01/11 15:53, 7年前 , 12F
下是要兩兩互質，不是GCD(2、3、15）=1，然後那題的81
01/11 15:53, 12F
→
01/11 15:53, 7年前 , 13F
不能拆是因爲拆出來的數也要是互質才行
01/11 15:53, 13F
→
01/11 15:56, 7年前 , 14F
不對，我好像又漏了什麼條件，這樣中興那題的9不能拆
01/11 15:56, 14F
→
01/11 15:56, 7年前 , 15F
成3*3，等其它神人補充好了SORRY TAT
01/11 15:56, 15F
→
01/11 15:58, 7年前 , 16F
中興資工那個9根本不用拆
01/11 15:58, 16F
→
01/11 15:58, 7年前 , 17F
不互質的時候需要做的事情是確認每條都相符
01/11 15:58, 17F
→
01/11 15:59, 7年前 , 18F
12跟21拆開時，得到都是1mod3，跟7mod9相符，所以可做
01/11 15:59, 18F
→
01/11 16:00, 7年前 , 19F
7mod9只有=>1mod3
01/11 16:00, 19F
→
01/11 16:13, 7年前 , 20F
R大請問，高第一的那題81為什麼不能拆呢？
01/11 16:13, 20F
→
01/11 16:15, 7年前 , 21F
就跟9不應該拆一樣啊
01/11 16:15, 21F
→
01/11 16:15, 7年前 , 22F
1mod3這件事情，在mod9裡面就是有1,4,7這三個東西
01/11 16:15, 22F
→
01/11 16:17, 7年前 , 23F
你要能拆，就是要只有一種可能才能拆
01/11 16:17, 23F
→
01/11 16:21, 7年前 , 24F
懂了，謝謝R大
01/11 16:21, 24F
→
01/11 16:59, 7年前 , 25F
了解了 感謝w大跟R大！！
01/11 16:59, 25F
推
01/11 18:20, 7年前 , 26F
想問為什麼7mod9 等價於1mod3 ?
01/11 18:20, 26F
→
01/11 18:25, 7年前 , 27F
不等價，書上寫錯了
01/11 18:25, 27F
‣ 更多 winson910343 的文章
文章代碼(AID): #1SE3DczQ (Grad-ProbAsk)