先上参考资料
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