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