当模数为素数时可以用费马小定理求逆元。
模数为合数时，费马小定理大部分情况下失效，此时，只有与模数互质的数才有逆元（满足费马小定理的合数叫伪素数，讨论这个问题就需要新开一个博客了）。
（对于一个数n，所有小于它且与它互质的数组成一个模n乘法群）
gcd是最大公约数，扩展gcd则是在一对数x,y的gcd后，给出一组解a,b，使得
a*x+b*y=gcd(x,y)
不难看出，如果将y是模数，并且x与y的gcd为1时
a*x+b*y=1
a*x % y=1
根据逆元的定义，此时a就是x的模y逆元。
int exgcd(int a,int b,int &x,int &y){ if(b==0){ x=1; y=0; return a; } int g=exgcd(b,a%b,x,y); int t=x; x=y; y=t-(a/b)*y; return g; }
原文：https://www.cnblogs.com/isakovsky/p/11291528.html