作者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