作者kevin770317 (pAnDa)
看板Grad-ProbAsk
標題[理工] 離散的模數乘法反元素 inverse of modulo
時間Mon Jan 18 00:09:14 2010
我是自學離散
看到模數乘法反元素這裡卡住了
我知道一般的乘法反元素 就是相乘後=單位元素
7*(1/7)=1
1是乘法單位元素,1/7是7的乘法反元素,反之7也是1/7的乘法反元素
(這個應該沒錯吧??)
現在我不瞭解的是,模數乘法反元素 是甚麼??
舉個例子來說(小黃第四版1-60頁的例38)
Find the inverse of 4 modulo 7.
7=1*4+3
4=1*3+1
=>1=4-3=4-(7-4)=-7+2*4
=>4*2等價1(mod 7)
所以4^-1=2(mod 7)
我自己目前有個想法但不知道正不正確
以這個例子 要找4的模數乘法反元素(在 mod 7)
就是找到一個數乘以4 然後除以7 餘1的數
這個數就是4的 模數乘法反元素 我這樣解釋有錯嗎??
還是根本連邊都沒摸到>"<???
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.224.238.35
1F：推 zeowo:標題錯誤 01/18 00:15
2F：推 tureday:7|4x-1 =>4x+7k=1...照你的說法是能找到解 不過一般解法 01/18 01:48
3F：→ tureday:還是4x+7k＝1去求 也就是gcd(4,7)=1,1＝4*（2）+7（-1） 01/18 01:52
4F：→ tureday:1=(2+7K)4+(-1-4K)*7 為其iverse ,而最小iverse為2 01/18 01:54
5F：→ doom8199:4 * 4^(-1) = 1 (mod 7) , 原po你那樣子解釋是對的~~ 01/18 02:03
6F：→ kevin770317:這樣是不是inverse會有無限多組 而2是最小的 是這樣嗎 01/18 08:16
7F：→ kevin770317:阿 原來二樓有講了 是有無限多組 但2為最小的 01/18 08:30
8F：→ kevin770317:謝謝各位^^" 01/18 08:30