预备知识
定义
这里我们只讨论整数中的乘法逆元。[1] 具体而言，如果在模 [math]\displaystyle{ p }[/math] 意义下，[math]\displaystyle{ ax\equiv 1(mod\ p) }[/math] ，我们就称 [math]\displaystyle{ x }[/math] 是 [math]\displaystyle{ a }[/math] 的乘法逆元。记作 [math]\displaystyle{ a^{-1}=x }[/math] 。
如果 [math]\displaystyle{ p }[/math] 是质数，那么对于任意的 [math]\displaystyle{ a\ne 0 }[/math] 都一定存在乘法逆元；如果 [math]\displaystyle{ p }[/math] 不是质数，那么可能存在 [math]\displaystyle{ a\ne 0 }[/math] 不存在乘法逆元。
用途
在处理过程中需要取模的问题时，可能会遇到除法。我们都知道，把取模过的数字相除无法得出原来的结果（即 [math]\displaystyle{ \frac{a\mod c}{b\mod c}\ne \frac{a}{b} }[/math] ），此时我们就需要用 [math]\displaystyle{ \times a^{-1} }[/math] 代替 [math]\displaystyle{ \div a }[/math] 。
另外，乘法逆元在加密算法（如RSA），扩展中国剩余定理算法等算法中有着重要意义。
做法
如何求取乘法逆元呢？这里介绍两种简单的方法。
费马小定理
根据费马小定理，我们有 [math]\displaystyle{ a^p\equiv a(mod\ p),\ p\ \ is\ \ prime }[/math] 。因此对于 [math]\displaystyle{ p }[/math] 是质数的情形，我们可以使用 [math]\displaystyle{ a^{p-2} }[/math] 作为 [math]\displaystyle{ a }[/math] 在模 [math]\displaystyle{ p }[/math] 意义下的乘法逆元。
这可以使用快速幂在时间复杂度 [math]\displaystyle{ O(\log p) }[/math] 内计算出来。
扩展欧几里得
我们都知道欧几里得的辗转相除法，有人从这一算法中得到启发发明了扩展欧几里得算法。
这一算法与裴蜀定理息息相关。裴蜀定理是说：[math]\displaystyle{ ax+by=c }[/math] 有解，当且仅当 [math]\displaystyle{ \gcd(a,b)|c }[/math] 。因此我们可以先解出 [math]\displaystyle{ ax+by=\gcd(a,b) }[/math] 的解集，然后再把 [math]\displaystyle{ x,y }[/math] 乘 [math]\displaystyle{ \frac{c}{\gcd(a,b)} }[/math] ，即可得出最后的解。 [2]
在辗转相除法中，我们知道 [math]\displaystyle{ \gcd(a,b)=\gcd(b,a\ mod\ b) , b\ne 0 }[/math] 。运用递归的思想，先求出 [math]\displaystyle{ bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)=\gcd(a,b) }[/math] 的解，然后再转化为原方程的解即可。
可以列出方程式 [math]\displaystyle{ ax+by=bx'+(a\ mod\ b)y' }[/math] ，其中 [math]\displaystyle{ x,y }[/math] 是未知数，其余的字母都是已知数。因为 [math]\displaystyle{ a\ mod\ b=a-a\lfloor \frac{a}{b} \rfloor }[/math] ，移项得到 [math]\displaystyle{ ax+by=a(y'-\lfloor \frac{a}{b}\rfloor y')+bx' }[/math] ，所以 [math]\displaystyle{ x=y'-\lfloor \frac{a}{b}\rfloor y',\ y=x' }[/math] 是原方程一组可行的解。
这样我们就得到了解方程 [math]\displaystyle{ ax+by=c }[/math] 的方法。
将“求模 [math]\displaystyle{ p }[/math] 意义下 [math]\displaystyle{ a }[/math] 的乘法逆元”这个问题转化一下，就可以改为求 [math]\displaystyle{ ax+py=1 }[/math] 这一问题中 [math]\displaystyle{ x }[/math]的解。显然可以使用裴蜀定理判断是否有解，然后使用exgcd（扩展欧几里得）解决。