作者mistel (Mistel)
看板Grad-ProbAsk
标题[理工] 离散 中国余数定理 鸽笼等
时间Sun Nov 24 22:34:47 2019
有几个困扰已久的问题...
1.
https://i.imgur.com/YB6AbA8.jpg
请问这题之所以mod8要换成mod4是因为
8|2x-4=2(x-2) => 4|x-2 这样吗？
2.
https://i.imgur.com/ijPwwdh.jpg
https://i.imgur.com/XTn4PZ1.jpg
请问在彼此不互质是应该怎麽判断才好？
像他说不可用2我完全不知道是为什麽，
并请问为什麽答案最後要取lcm(9,12,21)而不是取lcm(3,4,7)？
3.
https://i.imgur.com/kC3vuqk.jpg
https://i.imgur.com/Dz84s5e.jpg
请问这题的b小题用到的鸽笼原理
两个蓝圈圈起来的上下句到底是怎麽推得的？想好久...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.136.0.251 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1574606089.A.E2F.html
1F：→ Ricestone: 1.这里2跟8不互质，所以消的时候会连8一起变11/24 22:43
2F：→ Ricestone: 直接举例来说，因为2x=4mod8在mod8里面是有x=2跟x=6这11/24 22:45
3F：→ Ricestone: 两个结果11/24 22:45
4F：→ Ricestone: 2.不能用2就只是因为跟原本的联立方程式不等价而已11/24 22:49
5F：→ Ricestone: 而且这详解作法不对，mod9根本不用变11/24 22:57
请问是怎麽判断9可以留下来的？
是因为[1]这个等价类在mod9下包含於[1]在mod3之下吗？
6F：→ Ricestone: 只要确认7mod9跟另外那两个1mod3是相符的，那两个mod311/24 22:58
7F：→ Ricestone: 就能去掉，所以剩的是mod9,mod4,mod711/24 22:59
8F：推 mathtsai: 1.对 2.两两最大公因数不为111/24 22:59
9F：→ mathtsai: x = 12k+4 = 4*(3k+1) 如果用2来做 就不等价惹11/24 23:00
请问这边是怎麽判断是否跟原式等价的？还是不太懂...
10F：→ Ricestone: 3.看不太懂你想问什麽，不过2^(i-1)只有2的因数，11/24 23:08
11F：→ Ricestone: 而现在n已经说是奇数（没有因数2），所以当然互质11/24 23:08
喔喔因为他真的写的太绕了所以不懂上下文的关联性XD
12F：→ mathtsai: 3.写那麽神秘干嘛...把你第一个蓝笔的部分相减11/24 23:21
13F：→ mathtsai: 得n | 2^j - 2^i = 2^i*(2^(j-i) - 1) => n | 2^(j-i)-111/24 23:23
！！！原来如此，我懂了
14F：→ mathtsai: 鸽笼其实某题会了 下次出神秘一点的一样没想法11/24 23:25
15F：→ ok8752665: 离散一堆都是没看过根本没想法的==11/24 23:27
※ 编辑: mistel (223.136.0.251 台湾), 11/24/2019 23:28:15
※ 编辑: mistel (223.136.84.166 台湾), 11/24/2019 23:32:05
16F：→ Ricestone: 7mod9这个限制比1mod3来得强，有7mod9就不需要再讲mod311/24 23:32
17F：→ Ricestone: 一个合数的同余式本来就有拆成等价的因数的联立同余式 11/24 23:37
18F：→ Ricestone: 的办法，叫除法原理 11/24 23:38
谢谢，限制较强这边我懂了，
但我还是不懂要怎麽由x=12k+4=4(3k+1)
判断跟原本的联立式子等价？
这条式子不是也等於2(6k+2)吗
※ 编辑: mistel (223.136.84.166 台湾), 11/24/2019 23:57:31
19F：→ Ricestone: 12本来就是拆成3跟4，如果用理论的想法，3跟4的余数可11/24 23:59
20F：→ Ricestone: 以表达12种情况，如果是3跟2就只剩6种，一定有问题 11/24 23:59
21F：→ Ricestone: 用刚刚限制较强的想法也可以，4的限制就是比2多啊 11/25 00:00
Got it!!
※ 编辑: mistel (223.136.84.166 台湾), 11/25/2019 00:01:45
22F：推 iamawinner: 我是觉得，能2能整除的，4未必能整除 11/25 02:56
23F：推 zuchang: 楼上 那不就是4的限制比较大的意思吗:) 11/25 12:24