作者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/cn.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