乘法逆元一乘法逆元一

乘法逆元一

导入：分数取模

考虑一个式子 (x equiv dfrac{1}{2} (mod 7)) ，即求一个数 (x) ，它与 (dfrac{1}{2}) 模 7 的结果相同，称为 (x) 与 (dfrac{1}{2}) 对模 7 同余。

分数取模不同于整数取模，但我们仍可以利用模运算的性质解决此题。

模运算时两边同乘相同的数， 两边仍然同余。

所以将两边同乘 2，原式即化简为 (2xequiv 1 (mod 7)) ，即求解方程组 (2x-7y = 1) 。

因为 (gcd(2,7)=1)，所以接下来使用扩展欧几里得算法就可以解决。

简述：乘法逆元的定义

如果在一个群 (G) 中，对于一个数 (b) ， 存在乘法逆元且为 (x) ， 那么就有 (bx=xb=e) ，其中 (e) 为群 (G) 的单位元。

对于单位元 (e) 我们有 (eb=be=b)

定义太多不看版：

就是说如果 (x) 是数 (b) 的乘法逆元，那么 (a*b*x=a)

考虑有理数域(理解为全体有理数构成的集合，所有选择的数都是里面的)，对于一个数 (b) ，它的逆元就是 (dfrac{1}{b}) (注意这里不是模运算意义下的逆元)，而这里的单位元就是数字 1.

主线：模运算意义下的乘法逆元

首先，我们假设模数为一个质数，记为 (p) 。(模数为质数这个条件非常重要，在求解乘法逆元时我们会看到)

然后，接下来的讨论，我们都是在模意义下。(注意，之后的单个字母，表示的都是整数)

那么，我们定义一个数 (b) 的乘法逆元为(x) ，当且仅当 (bxequiv1 (mod p))

为什么会这么定义呢？

显然，我们有 (a*b*xequiv a (mod p)) ，这不就是乘法逆元的定义吗，只不过是在模运算下的。

这样有什么用呢？

考虑式 (xequiv dfrac{1}{b} (mod p))

两边同乘 (a) ，得到 (axequiv dfrac{a}{b} (mod p))

...对比一下分数取模中的式子，是不是感觉有点熟悉...

最简单的，我们发现了，数 (b) 的乘法逆元 (x) ，在模意义下，同余于 (dfrac{1}{b}) ，即前文的 (xequiv dfrac{1}{b} (mod p))

进一步，我们发现，这样就可以清楚地定义分数取模的解决方法了。

对于式子 (cequiv dfrac{a}{b} (mod p)) ，我们只需要计算 (b) 的乘法逆元 (x) ，那么原式就可以化简为 (cequiv ax (mod p))

前行：关于乘法逆元的求解

如果模数 (p) 为质数

首先，根据费马小定理，我们有 (b^{p-1}equiv 1 (mod p))

...显然，数 (b) 的逆元即为 (b^{p-2})

如果 (p) 不为质数呢

费马小定理只适用于 (p) 为质数的情况，但是，我们有更通用的算法，欧拉定理。

如果 (p) 与 (b) 互质，那么我们就可以使用欧拉定理来求解。

欧拉定理的表示如下 (b^{varphi(p)-1}equiv1 (mod p))

其中 (varphi(x)) 定义为 1 到 (x) 之间与 (x) 互质的数的个数。

当然，也可以使用扩展欧几里得算法。

那么，如果 (p) 与 (b) 不互质呢？

往下看。

深入：关于模意义下乘法逆元更深层的一些讨论

1. 模逆元的存在性:当 (p) 与 (b) 不互质时，模意义下的乘法逆元，不存在

我们回顾一下乘法逆元的定义：我们定义一个数 (b) 的乘法逆元为(x) ，当且仅当 (bxequiv1 (mod p))

我们改写一下这个式子: ((kr)*x -1=cr) ，其中 (r=gcd(p,b)neq 1) ， (kr=b) ， (cr=q*p) ( (p) 的某个倍数)

..好了，已经可以发现 (kr*x) 和 (cr) 都为 (r) 的倍数，但是因为 (rneq1) ，所以 (1) 不为 (r) 的倍数。

这说明等式不成立，即乘法逆元不存在。

2.模逆元 (x) 一定为整数吗

首先，模逆元定义为 (x) 整数。

其次，定义为分数并没有解决问题，比如我有 (b*dfrac{1}{b}equiv1 (mod p)) ...

可以知道的是，模运算对于加减乘三种运算具有很好的性质，但是对于除法却不是很好，所以我们是要将除法化为乘法。

3.在OI中的应用

我们知道，在OI中，通常数据是有限制的，此时出题人一般会给你一个模数 (p)

比如计数类问题，还有分数需要保持精度的问题。

而模运算将除法变成乘法后，就可以有效利用乘法在模运算中的性质，举例：

我们要计算 (dfrac{a}{b} mod p) ，就可以化为 (((a mod p)*(x mod p)) mod p) ，其中 (x) 为 (a) 的逆元。

这样就可以大幅度降低数据大小，同时保证除法的精度。