數論解模同餘方程式 silence0925 PTT批踢踢實業坊

作者: silence0925 (小文青) 2018-09-23 20:00:19

b小題的答案
https://i.imgur.com/VMjfnAy.jpg
我的過程
我算出來的答案會有少是為什麼阿
然後為什麼會變成 x=7 (mod27)
https://i.imgur.com/TZX3qQ4.jpg
麻煩各位大大幫忙解個惑

作者: meokay (我可以) 2018-09-23 20:08:00

等價 8X + 27Y = 2 <=> 8X同餘2（mod27）

作者: kyuudonut (å–„è‰¯è€ç™¾å§“) 2018-09-23 20:13:00

因為 24 跟 81 不互質，這樣找不到所有解的。

作者: skyHuan (Huan) 2018-09-23 21:55:00

因為有公因數，要除掉公因數才是所有解集合https://imgur.com/611X4jO.jpg8*81=27*24. 才是最小公倍數所以x跟-20+54k同餘，代k=0, 1, 2

作者: silence0925 (小文青) 2018-09-23 22:17:00

懂S大的說法但不懂m大的等價該怎麼看另外s大那個解也不是所有解集合欸 _

作者: skyHuan (Huan) 2018-09-23 22:31:00

k=0, 1, 2分別是-20, 34, 88 (mod 81)=61, 34, 7等價可以看成第一步81k=24x-6就除掉公因數了除掉公因數就互質了，用歐幾里得演算法每次就是加27，但原題是mod 81所以超過81才進位

作者: silence0925 (小文青) 2018-09-23 22:40:00

哦哦原來還要再取mod 81 我以為那就答案了所以可以一開始除掉公因數不會有問題的嗎

作者: skyHuan (Huan) 2018-09-23 22:45:00

你把一開始先除掉做完的結果寫出來跟直接做再除掉公因式的結果會一樣，其實是同一件事，只是要小心一開始先除的話做完結果是mod 27，但題目是mod 81，所以不要看算出來超過27就把他縮到27以內

作者: silence0925 (小文青) 2018-09-23 22:46:00

哦哦哦哦哦懂了感謝s大細心講解

繼續閱讀