算法提高篇--数学基础（五）：逆元
不学不知道，算法真奇妙。又到了将“算法”刻到骨子里的时刻，今天为大家带来的是数学基础的第五讲——模意义下乘法运算的逆元(Modular Multiplicative Inverse)。
1、引入
在数据非常大的情景下，我们通常会对数据取模运算来规定在一定的范围内进行处理。而运算的过程中，针对(a+b)%p,(a-b)%p和(a*b)%p，我们都可以通过运用分配律将数据维护在合理的范围内进行精确计算，即(a+b)%p = (a%p+b%p)%p、(a-b)%p=(a%p-b%p)%p和(a*b)%p=(a%p*b%p)%p，即当a和b很大时，我们可以先取模将数据降区间后再进一步计算。但是对于(a/b)%p，它是不满足分配律的，那怎么办呢？对于一些数据，我们必须在中间过程先对其进行求余后再运算，否则数据将会太大，在计算机中进行除法运算的时候可能会损失精度，导致答案变小，那怎么才能解决这个问题呢？
首先，我们先来了解剩余系相关的知识点：剩余系是指模正整数n的余数所组成的集合。如果一个剩余系中包含了这个正整数n所有可能的余数（0,1,2,....,n-1），则称为其是模n的一个完全剩余系，记做Zn。完全剩余系中与n互素的数组成简化剩余系，记做
。
Zn里的每一个元素代表所有模n意义下与它同余的整数。例如n=9时，Z9的元素3实际上代表3、12、21、30...、9k+3（k为自然数）这些模9等于3的数。而这些满足同余关系的所有整数叫做同余等价类。
在Zn中，四则运算都要在模n的意义下，如Z12中，9+3=0,2*6=0。因此，在模运算中，我们知道，减法可以通过补数转化为加法，如在时钟系统中，(8-2)12 = 6，模12的系统中，2的补数是10，因此8-2可以转化为加法运算：(8+10)12 = (8+4+6)12 = (12+6)12 = 6（注，最终的结果不能超过12，即都要模12，相当于以12为周期）。同样，除数如果存在逆元的话，除法也可以转化为乘法，即除以一个数等于乘上这个数的逆元。如在模取9的系统中，(7÷2)9 = (7×5)9。那么，什么是逆元呢？
2、逆元
如果一个线性同余方程ax≡1(mod b)，则x称为a mod b的逆元，记做a^(-1)。换一种表述方式：在模n的意义下（Zn）的两元素a和b（指以n为模的系统里，如时钟的计量范围是0~11，时钟就是以12位模的系统），满足a*b=1，比如在模为9的系统中，(2*5)%9 = 1，那么我们就说a、b互为模n意义下乘法的逆元，记做a = b^(-1)，b = a^(-1)。如2和5互为模9意义下乘法的逆元，记做2 = 5^(-1)。
那么开始的例子中7÷2在模9的系统中是什么意思呢？我们知道剩余系中的每一个元素都对应一个同余等价类，所以7÷2的实际含义是：假定有两个整数a、b，满足a/b是整数），且a和b除以9的余数分别是7和2，那么a/b除以9的余数等于(7÷2)9= (16÷2)9=8%9=8。而(7×5)9=8。即(7÷2)9 = (7×5)9=8。
当a、m互素时，若ax≡1(mod m)，则称x是a关于模m的逆元，记做a^(-1)。且在[0,m)范围内，a的逆元是唯一的。
证明（反证法证明唯一性）：
若a有两个逆元0＜x1<x2<m，即：ax1≡ax2≡1(mod m)。
那么显然有m|a(x2-x1)成立，又gcd(a,m)=1。
因此m|(x2-x1)，即0<m<x2-x1。与0＜x1<x2<m矛盾。故假设不成立。
又在概述中可以发现将一个整数乘以a^(-1)等价于这个整数除以a，即在模意义下将除法转化为了乘法。即：(a/b)%m = (a*b^(-1))%m（注：这里b^(-1)是在模m的系统下的）。那么，问题又来了，如何求逆元呢？我们需要先了解以下几个概念！
3、费马小定理
若p为素数，且a和p互素，则有a^(p-1)≡1(mod p)。
证明：∵p为素数，且a和p互素
∴a从1到(p-1)的倍数，即a,2a,3a,...,(p-1)a中没有一个是p的倍数，而且任意两个数模p都不同余。
∴a,2a,3a,...,(p-1)a这(p-1)个数对模p的同余是1,2,...,(p-1)的排列。
∴a*2a*3a*...*(p-1)a≡1*2*...*(p-1)(mod p)。
即a^(p-1)*(p-1)!≡(p-1)!(mod p)。
即a^(p-1)≡1(mod p)得证。
易得，对于任意整数a，若p为素数，则有a^p≡a(mod p)。
费马小定理的应用就是转化，当p为素数，a和p互素时，则:
a^b(mod p) = a^(b mod (p-1))(mod p)。
如p=5,a=3时，3^4(% 5)=81%5=3^(4%4)%5=1。即3^4≡1(mod 5)。在求解3^(2046)%5时，就可以转化为3^(4*511+2)≡3^2(mod 5)≡4(mod5)。
4、欧拉定理
我们先了解欧拉函数（Euler's totient function），即φ(n)，表示的是小于等于n的数中和n互质的数的个数。如果φ(1) =1。当n是质数的时候，显然有φ(n) = n-1。
欧拉定理内容为：若gcd(a,m)=1，则a^(φ(m))≡1(mod m)。证明的过程可以参考费马小定理的证明思路，即构造一个与m互质的数列，不同的是用到的简化剩余系。
例如：m=10,a=3时，φ(10) = 4，3^(φ(10)) = 3^4 ≡ 1(mod 10)。
显然，当m是素数是，φ(m) = m-1，代入可得：a^(m-1) ≡ 1(mod m)，即欧拉定理是费马小定理的加强版。
当a和m互素时，且m>1时，可得：a^b(mod m) = a^(b mod φ(m))(mod m)。
证明：设b = q*φ(m) + r，其中0≤r＜φ(m)，即r = b%φ(m)。
a^b = a^(q*φ(m) + r) = (a^φ(m))^q*a^r。
∵a和m互素
∴a^b≡(a^φ(m))^q*a^r ≡ 1^q* a^r≡ a^r≡ a^(b%φ(m))(mod m)。
我们用欧拉定理即可求得逆元：
a^(φ(m)) = a^(φ(m)-1)*a≡1(mod m)。由逆元的定义，得a在模m意义的乘法逆元就是a^(φ(m)-1)。
特别的，当m是素数是，φ(m) = m - 1，即a^(m-2)≡a^(-1)(mod m)。所以，在实际应用中，当我们求(a/b)%p时，当p是素数是，就可以将其转化为求(a%p*b^(p-2)%p)%p。
5、模板
在信竞中，求逆元通常是解题过程中处理大数除法并对某个素数取模的利器，解题模板如下：
typedef long long ll;ll mod ;//某个较大的素数ll quickPowWithMod(ll a,ll b){ll res = 1;while(b){if(b&1) res = res*a%mod;a = a*a%mod;b>>=1;}return res%mod;}/**处理(a/b)%mod*/ll div(ll a,llb){return (a%mod)*quickPowWithMod(b,(mod-2))%mod;}
6、小结
本讲文字叙述较多，尽量做到用一个又一个问题来过渡和衔接，能够理解最好，一时不能悉数理解也很正常（毕竟笔者面向的很多是中学生）。其实不妨先记住结论，其实说到底就是要把除法并求模过程，转化变成乘上除数的逆元后求模，而核心步骤则是利用欧拉定理快速实现逆元的求解。以上就是本讲的内容，关于逆元的应用将在以后的章节里进一步与大家一起分享和学习，谢谢大家的时间。