UC知道数论，关于求乘法逆元素
来源：百度知道 编辑：UC知道 时间：2024/05/16 11:51:00
知道一个数的模怎么求他的乘法逆元素啊？
比如求143^-1（mod7）=5(mod7)
我知道5*143=1（mod7)
因此5是143的乘法逆元素，可是这个5是怎么得出来的啊？
也就是如果只知道143和7这两个数，怎么求得5是143（mod7）的乘法逆元素.
我资料上写的是用欧拉公式得出来的，怎么得出来的？
谢谢。懂了再加分~~~~~~~~~
比如求143^-1（mod7）=5(mod7)
我知道5*143=1（mod7)
因此5是143的乘法逆元素，可是这个5是怎么得出来的啊？
也就是如果只知道143和7这两个数，怎么求得5是143（mod7）的乘法逆元素.
我资料上写的是用欧拉公式得出来的，怎么得出来的？
谢谢。懂了再加分~~~~~~~~~
143=3mod7
3*5=15=1mod7
1/143mod7=7n+1/13*11mod7
n=3 ,7n+1=22
22/11*13mod7
2/13mod7即7n+2/13
n=9时7n+2=65
65/13=5mod7
11*13mod7
4*6mod7
24mod7
3mod7
用欧拉定理吧
设f（p）为欧拉函数（就是那个fai（p），那个fai打不出来）
143^f(p)同余于1(modp)
则143^(f(p)-1)即为143modp的逆，在p=7的情景下，143^(f(p)-1)同余于5
这个似乎不太实用，计算量很大的