查看“算法: 求模意义下的乘法逆元”的源代码

==预备知识==
[[模运算]]

==定义==
这里我们只讨论整数中的乘法逆元。<ref>OI-wiki中更详细的介绍</ref>
具体而言，如果在模 <math>p</math> 意义下，<math>ax\equiv 1(mod\ p)</math> ，我们就称 <math>x</math> 是 <math>a</math> 的乘法逆元。记作 <math>a^{-1}=x</math> 。

如果 <math>p</math> 是质数，那么对于任意的 <math>a\ne 0</math> 都一定存在乘法逆元；如果 <math>p</math> 不是质数，那么可能存在 <math>a\ne 0</math> 不存在乘法逆元。

== 用途 ==
在处理过程中需要取模的问题时，可能会遇到除法。我们都知道，把取模过的数字相除无法得出原来的结果（即 <math>\frac{a\mod c}{b\mod c}\ne \frac{a}{b}</math> ），此时我们就需要用 <math>\times a^{-1}</math> 代替 <math>\div a</math> 。

另外，乘法逆元在加密算法（如[[RSA]]），[[扩展中国剩余定理算法]]等算法中有着重要意义。

== 做法 ==
如何求取乘法逆元呢？这里介绍两种简单的方法。
=== 费马小定理 ===
根据[[费马小定理]]，我们有 <math>a^p\equiv a(mod\ p),\  p\ \ is\ \ prime</math> 。因此对于 <math>p</math> 是质数的情形，我们可以使用 <math>a^{p-2}</math> 作为 <math>a</math> 在模 <math>p</math> 意义下的乘法逆元。

这可以使用[[快速幂]]在时间复杂度 <math>O(\log p)</math> 内计算出来。
=== 扩展欧几里得 ===
我们都知道欧几里得的[[辗转相除法]]，有人从这一算法中得到启发发明了[[扩展欧几里得]]算法。

这一算法与[[裴蜀定理]]息息相关。裴蜀定理是说：<math>ax+by=c</math> 有解，当且仅当 <math>\gcd(a,b)|c</math> 。因此我们可以先解出 <math>ax+by=\gcd(a,b)</math> 的解集，然后再把 <math>x,y</math> 乘 <math>\frac{c}{\gcd(a,b)}</math> ，即可得出最后的解。 <ref>详情见 oi-wiki贝祖定理</ref>

在辗转相除法中，我们知道 <math>\gcd(a,b)=\gcd(b,a\ mod\ b) , b\ne 0</math> 。运用[[递归]]的思想，先求出 <math>bx'+(a\ mod\ b)y'=\gcd(b,a\ mod\ b)=\gcd(a,b)</math> 的解，然后再转化为原方程的解即可。

可以列出方程式 <math>ax+by=bx'+(a\ mod\ b)y'</math> ，其中 <math>x,y</math> 是未知数，其余的字母都是已知数。因为 <math>a\ mod\ b=a-a\lfloor \frac{a}{b} \rfloor</math> ，移项得到 <math>ax+by=a(y'-\lfloor \frac{a}{b}\rfloor y')+bx'</math> ，所以 <math>x=y'-\lfloor \frac{a}{b}\rfloor y',\  y=x'</math> 是原方程一组可行的解。

这样我们就得到了解方程 <math>ax+by=c</math> 的方法。

将“求模 <math>p</math> 意义下 <math>a</math> 的乘法逆元”这个问题转化一下，就可以改为求 <math>ax+py=1</math> 这一问题中 <math>x</math>的解。显然可以使用裴蜀定理判断是否有解，然后使用exgcd（扩展欧几里得）解决。