[理工] 離散 中國餘數定理 鴿籠等

看板Grad-ProbAsk作者 (Mistel)時間4年前 (2019/11/24 22:34), 4年前編輯推噓3(3推 0噓 20→)
留言23則, 5人參與, 4年前最新討論串1/1
有幾個困擾已久的問題... 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1574606089.A.E2F.html
→
11/24 22:43, 4年前 , 1F
1.這裡2跟8不互質，所以消的時候會連8一起變
11/24 22:43, 1F
→
11/24 22:45, 4年前 , 2F
直接舉例來說，因為2x=4mod8在mod8裡面是有x=2跟x=6這
11/24 22:45, 2F
→
11/24 22:45, 4年前 , 3F
兩個結果
11/24 22:45, 3F
→
11/24 22:49, 4年前 , 4F
2.不能用2就只是因為跟原本的聯立方程式不等價而已
11/24 22:49, 4F
→
11/24 22:57, 4年前 , 5F
而且這詳解作法不對，mod9根本不用變
11/24 22:57, 5F
請問是怎麼判斷9可以留下來的？ 是因為[1]這個等價類在mod9下包含於[1]在mod3之下嗎？
→
11/24 22:58, 4年前 , 6F
只要確認7mod9跟另外那兩個1mod3是相符的，那兩個mod3
11/24 22:58, 6F
→
11/24 22:59, 4年前 , 7F
就能去掉，所以剩的是mod9,mod4,mod7
11/24 22:59, 7F
推
11/24 22:59, 4年前 , 8F
1.對 2.兩兩最大公因數不為1
11/24 22:59, 8F
→
11/24 23:00, 4年前 , 9F
x = 12k+4 = 4*(3k+1) 如果用2來做 就不等價惹
11/24 23:00, 9F
請問這邊是怎麼判斷是否跟原式等價的？還是不太懂...
→
11/24 23:08, 4年前 , 10F
3.看不太懂你想問什麼，不過2^(i-1)只有2的因數，
11/24 23:08, 10F
→
11/24 23:08, 4年前 , 11F
而現在n已經說是奇數（沒有因數2），所以當然互質
11/24 23:08, 11F
喔喔因為他真的寫的太繞了所以不懂上下文的關聯性XD
→
11/24 23:21, 4年前 , 12F
3.寫那麼神秘幹嘛...把你第一個藍筆的部分相減
11/24 23:21, 12F
→
11/24 23:23, 4年前 , 13F
得n | 2^j - 2^i = 2^i*(2^(j-i) - 1) => n | 2^(j-i)-1
11/24 23:23, 13F
！！！原來如此，我懂了
→
11/24 23:25, 4年前 , 14F
鴿籠其實某題會了 下次出神秘一點的一樣沒想法
11/24 23:25, 14F
→
11/24 23:27, 4年前 , 15F
離散一堆都是沒看過根本沒想法的==
11/24 23:27, 15F
※ 編輯: mistel (223.136.0.251 臺灣), 11/24/2019 23:28:15 ※ 編輯: mistel (223.136.84.166 臺灣), 11/24/2019 23:32:05
→
11/24 23:32, 4年前 , 16F
7mod9這個限制比1mod3來得強，有7mod9就不需要再講mod3
11/24 23:32, 16F
→
11/24 23:37, 4年前 , 17F
一個合數的同餘式本來就有拆成等價的因數的聯立同餘式
11/24 23:37, 17F
→
11/24 23:38, 4年前 , 18F
的辦法，叫除法原理
11/24 23:38, 18F
謝謝，限制較強這邊我懂了， 但我還是不懂要怎麼由x=12k+4=4(3k+1) 判斷跟原本的聯立式子等價？ 這條式子不是也等於2(6k+2)嗎 ※ 編輯: mistel (223.136.84.166 臺灣), 11/24/2019 23:57:31
→
11/24 23:59, 4年前 , 19F
12本來就是拆成3跟4，如果用理論的想法，3跟4的餘數可
11/24 23:59, 19F
→
11/24 23:59, 4年前 , 20F
以表達12種情況，如果是3跟2就只剩6種，一定有問題
11/24 23:59, 20F
→
11/25 00:00, 4年前 , 21F
用剛剛限制較強的想法也可以，4的限制就是比2多啊
11/25 00:00, 21F
Got it!! ※ 編輯: mistel (223.136.84.166 臺灣), 11/25/2019 00:01:45
推
11/25 02:56, 4年前 , 22F
我是覺得，能2能整除的，4未必能整除
11/25 02:56, 22F
推
11/25 12:24, 4年前 , 23F
樓上 那不就是4的限制比較大的意思嗎:)
11/25 12:24, 23F
‣ 更多 mistel 的文章
文章代碼(AID): #1TsfK9ul (Grad-ProbAsk)