好啦上次講過快速冪之後
這次要來講另一個超實用小技巧啦
隆重介紹我們的……模逆元！！！
……好啦我在自嗨不要理我
但是真的常常用到啦
先說說要學模逆元的原因
為什麼會有模逆元這種鬼東西出現呢？
因為 在做模運算的時候
加法 減法 乘法都能正常運作
(8+7)%5=(8%5+7%5)%5
(8-7)%5=(8%5-7%5)%5 (註)
(8*7)%5=((8%5)*(7%5))%5
但是
同樣的模式不能推導到除法
例如(56/7)%5不等於((56%5)/(7%5))%5
這時候就需要用到模逆元了！
那麼 就開始這次的內容吧~
(應該大部分的人都知道了
不過我還是再提一次好了
mod表示模運算 也就是求餘數
例如17 mod 5就是17除以5的餘數=2
在C++中用%表示)
模逆元 又稱為模反元素
在說模逆元之前
先來說說單位元素是什麼吧
某種二元運算下(加法、乘法、……)的單位元素的定義是
任意一個元素和單位元素做了這種運算之後
得到的結果等於原本的那個元素
例如 加法的單位元素是0
因為任何一個數字n加上0依然是n
乘法的單位元素是1
因為任何一個數字n乘上1依然是n
方陣乘法的單位元素是單位方陣
因為任何方陣乘上單位方陣之後依然是它自己
之後就要來說反元素了
比較簡單的說法是
如果一個元素x和另一個元素k做某種運算
使得結果為單位元素
那麼k就是x在這種運算下的反元素
例如說
3的加法反元素是 -3
因為3+(-3)=0
3的乘法反元素是1/3
因為3*(1/3)=1
或是 任意方陣的反元素就是它的反方陣
因為一個方陣乘上它的反方陣等於單位方陣
接下來要進入主題囉
顧名思義 模反元素就是在模運算下的反元素
或者可以說是 在模運算下的乘法反元素
也就是說
如果(a*b)%n=1
則b就是a的反元素
有時會用a^(-1)表示
例如說
在mod 5的時候
3的模反元素是多少呢？
答案是2
因為3*2除以5的餘數是1
那麼 它要如何幫助我們做除法運算呢？
在四則運算中
除以一個數字相當於乘上那個數字的乘法反元素(也就是倒數)
而加上模運算後
除以某個數字就變成以「乘上那個數字的模反元素」代替啦
以上面的例子舉例
(56/7)%5
這時候要計算(7%5)在mod 5 的時候的模反元素
因為(2*3)%5=1
所以2(或者說7)在mod 5時的模反元素是3
因此
(56/7)%5可以改寫成(56*3)%5
變成乘法之後就可以拆開做啦
[(56%5)*(3%5)]%5=3
Bingo~
另外 補充個小東西
不是所有情況下都能找到模反元素哦
例如 mod 6的時候
如果要除以3
很明顯3乘上任意數字再%6
結果不是0就是3
絕對不可能餘1
這種情況下 模反元素是不存在的
好啦 這次的教學文就到這裡告一段落啦
蛤？你說跟寫程式有什麼關係？
沒看到我標題就寫(一-0)齁
這叫前情提要！(爆氣ing)
好啦
因為光數學的部分就很麻煩了
再加上程式設計的話
這篇文大概沒人能看完@@
下一篇就是程式設計上的模逆元啦
敬請期待~
你可能有興趣的文章...
全部留言
就在下一篇啦 快到了！ 總是要先把一個主題講完的 然後啊 我還要研究一下怎麼表示矩陣@@ 所以再等我一下拜託🙏🙏
匿名
https://i.imgur.com/tENJH18.jpg https://i.imgur.com/uwS5jA7.jpg QWQ https://i.imgur.com/ppbblGg.jpg
{{comments[2].isShow ? '收合' : '展開' }}1則留言
匿名
我昨天考離散數學考到心很累😫😫
{{comments[3].isShow ? '收合' : '展開' }}1則留言
@@ 先祝你考試順利成績滿意啦 然後啊 其實數學可以很有趣的啦 (呃呃 以非大學生的身份 我覺得看起來還滿有趣的啦 至於以後它和我的成績有關的時候我就不確定了@@) 不過 引一句我表姐說的 擇己所愛 愛己所擇 既然選擇了往資工的方向走 就試著找出它精彩的地方吧~
匿名
大概不會滿意了☹️☹️ 其實數學真的很好玩阿 我是完全認同 但從國中開始我就知道自己喜歡數學 但討厭數學考試xddd 不知道自己為何選這條🙁 謝謝你😭😭
{{comments[4].isShow ? '收合' : '展開' }}1則留言
別這麼說啦 人生總是會有很多驚喜的XD 如果只是討厭考試的話 就不要把它當考試啦 把它當作是腦力激盪 還有對自己的挑戰 就不會討厭它了 (我是認真的 雖然這樣做 考試成績不會到頂尖 但是換一個心態 不去排斥它的時候 結果不會太差的) 呃呃 不管是為了就業 為了興趣 或是單純為了一份夢想 甚至是賭氣 (就像我XD 高中學資訊學老半天結果填了一個和資工完全無關的科系) 我相信 會有個一開始選擇它的理由啦 說句不好聽的 從頭來過也不是一件輕鬆的事 而且再一次的選擇 也不一定能選到一條更適合自己的路 另外 資訊是這個時代最熱門的一個領域 學會了除了就業之外 在其他方面也或多或少有一些幫助 所以 如果沒有明確想要往什麼方向走的話 不妨繼續向前邁進 即使找不回當初選擇的理由 也能找到留下奮鬥的動力 這是我的看法 祝福你~
匿名
B8 計算機概論也有提到一點點關於密碼學的東西 但都只是沾點邊而已 我有個室友是鳳山高中的欸
匿名
離散包山包海 很多東西都有ww 我也不知道怎麼說 https://i.imgur.com/50oSkLu.png https://i.imgur.com/paRRSnq.png https://i.imgur.com/S4ClZY9.png 密碼學算是應用🤔
B16 已違反板規，以此留言勸導，請於期限內改善。 違規事實：留言和文章及前面的留言內容無任何關聯，經板主認定屬於鬧板。 改善期限：2018/7/26 下午12:44 逾期未改善者，依 第四條-一-(五) 之規定刪文及水桶3天處理。
