先上参考资料 https://www.bilibili.com/video/av35557954 https://blog.csdn.net/AAMahone/article/details/79320635

首先要明确，乘法逆元是什么

对于ax mod p = 1 这时，x就是a 在mod p乘法群的乘法逆元 那只介绍一种求逆元的方法。 就是通过拓展欧几里得算法，得到ax + py = gcd（a，p） 因为a属于模p乘法群，所以a<p，所以a与p互素，则有gcd(a,p)=1 即 ax + py = 1 有了这个，我们就可以两边求mod p 即有 ax = 1（mod p），即此时的x就是乘法逆元。

#include<iostream> using namespace std; int exgcd(int a,int b,int &x,int &y){ if(b==0) { //最里面ax+0=a的情况,注意此时a经过多次递归已经不是刚开始的啊 x=1; y=0; return a; } //要先调用ngcd来进到最里层确定x，y的值，从逐步到外层计算出x，y int ngcd = exgcd(b,a%b,x,y); //根据相关理论有如下的逆公式 x==y1,y==x1-a/b*y1 int temp = x; x = y; y = temp - a/b*y; return ngcd; } int inverse(int a, int p){ int x,y,gcd; gcd = exgcd(a,p,x,y); if(gcd==1){ x=(x%p+p)%p;//保证x为正数; return x; } else{ cout<<"a,p不互质"; return 0; } } int main(){ //实际上是求ax + py = gcd(a,p) = 1 /a,p互质 int a,p; cout<<"请输入 a p"<<endl; cin>>a>>p; cout<<"a mod p的乘法逆元是"<<inverse(a,p); return 0; }

python

def ext_gcd(a, b): if b == 0: x1 = 1 y1 = 0 x = x1 y = y1 r = a return r, x, y else: r, x1, y1 = ext_gcd(b, a % b) x = y1 y = x1 - a / b * y1 return r, x, y