之前学过用快速幂求逆元，条件是当模数 \(p\) 为质数的时候，\(a\) 的逆元就是 \(a^{p - 2}\)。
但相较于扩展欧几里得算法求逆元，适用的范围是比较小的，因为扩展欧几里得算法适用于所有逆元存在的情况。
在以下的式子中，模数为 \(m\) 的情况下，\(x\) 就是 \(a\) 的逆元
\[ax\equiv1(mod~m)
\]
转化一下式子，可以得到 \(ax +ym=1\) (\(y\) 是一个新的变量)
根据线性同余方程的性质，有解的条件是\(gcd(a, m)|1\)（左边能整除右边），所以只在 \(gcd(a, m)=1\) 的时候有解
也就证得，\(a\)与\(m\)互质的时候逆元有解
再复习一下扩展欧几里得算法，它可以解得 \(ax+by=gcd(a, b)\) 中 \(x,y\) 的值
因为 \(gcd(a, m)=1\)，\(ax+ym=1\)
所以只要逆元存在（要求的数与模数互质），都可以用扩展欧几里得算法求
最后
扩展欧几里得算法求逆元的方式就是
int x, y;
exgcd(a, m, x, y);
return (x % m + m) % m;