為什麼這篇mod題目鄉民發文收入到精華區：因為在mod題目這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者HiltonCool (野獸瘋)看板Grad-ProbAsk標題Re: [理工] [離散]Fin...
mod題目 在 Peiyu 高珮喻 페위 Instagram 的最讚貼文
2021-01-05 16:05:29
今年過年，米糕不用自己做哦！買阿發師的就可以了！ @2020tchintchin - 其實為了備賽，我請教了阿發師並且在青青餐廳練習。感謝無私奉獻的阿發爸、Jeff哥！那天晚上知道題目，立刻想到一代宗師味香濃郁的米糕。趕緊聯繫Jeff哥和阿發爸，兩位超級支持，一口答應！隔天大清早的我們在青青餐廳開...
※ 引述《yoyotvyoo (yoyotvyoo)》之銘言：
: 題目：
: Find the inverse of 4 modulo 7.
: 解答：
[步驟一] 利用 Euclidean algorithm 求 4 與 7 的線性組合
7 = 1 x 4 + 3
4 = 1 x 3 + 1
[步驟二] 利用上述的結果由下往上整理出 1 = xxx
4 = 1 x 3 + 1 //從最後一條式子開始推導
=> 1 = 4 - (1 x 3) //把 1 留在等號左邊，其餘丟到右邊
= (-1) x 3 + 4 //觀察上一條式子([步驟一]第一式)的最右邊是 3
所以你的下一個步驟會把 3 代換掉
把 3 移到前面，待會會比較好整理
= (-1) x (7 - (1 x 4)) + 4 //利用[步驟一]第一式把 3 換成 7 - (1 x 4)
然後帶入上式
= 4 x 2 + 7 x (-1) //將上式整理之後就會得到此式
[步驟三] 寫答案
因為 7 x (-1) 在 mod 7 之下為 0
所以[步驟二]的式子會變成 1 = 4 x 2 (記得都是在 mod 7 的情況下討論的)
=> 4 x 2 ≡ 1 (mod 7)
所以 2 為 4 在 mod 7 下的一個乘法反元素
Ans：4 在 mod 7 下的所有乘法反元素為 2 + 7k ,∀k∈R
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.168.59
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1409246372.A.0B4.html
※ 編輯: HiltonCool (114.42.168.59), 08/29/2014 01:23:42
推 yoyotvyoo: 謝謝你！但是最後面 7 x (-1) 消掉之後 08/29 08:34
→ yoyotvyoo: 1 = 4 x 2 (mod 7) 這條怎麼變成 4 x 2 ≡ 1 (mod 7)? 08/29 08:35
→ lovebnn: 其實寫等號是有問題的，嚴謹一點應寫成≡. 不過既然已強 08/29 08:48
→ lovebnn: 調是在mod 7下討論，倒也無妨。但如果是初學者仍應避免。 08/29 08:48
→ lovebnn: 你可以把倒數第四行略過，我想這樣看反而比較清楚。 08/29 08:50
→ HiltonCool: 這一行只是為了讓原po容易理解，考試時不用寫出來 08/29 09:40
→ HiltonCool: 當題目要求的是 mod 7 的時候，注意你接下來的解題步 08/29 09:45
→ HiltonCool: 全部都是在 mod 7 之下討論的 08/29 09:46
推 yoyotvyoo: 弄懂了！謝謝你們的幫忙！ 08/29 15:54