乘法逆元（inverse element）及四大相关求法详解（含证明）

大家好，欢迎来到IT知识分享网。

乘法逆元及四大相关求法详解（含证明）

知识的补缺是老生常谈的一大问题，随着自身学习进程的推进，越发觉着逆元知识的重要，故此我站在网上各路大牛的肩膀上，对此知识进行一定程度上的系统梳理。如有不足之处，还请大家指出，大家共同进步，互利共赢 ！！

开胃菜

先呈上菜：

很明显，上述式子只有一条不成立，即 ( a / b ) % m，但有些情况下，又需要进行有模运算的除法。由于式子不成立，当 a 过大或者 b 过大时，极易导致计算过程丢失精度，造成结果误差。因此，为了避免这一遭，逆元就应运而生了。

1. 定义及理解

1.1 乘法逆元的定义

1.1.1 极简定义

​ 在 模m 有意义的条件下， 若 ax ≡ 1 ( mod m ）, 则称 a 关于 1 模 m的乘法逆元为 x

1.1.2 详细定义

​ 若整数 a，m 互质，并且对于任意的整数 b，如果满足 a | b ( a 能整除 b )，则存在一个整数 x，使得 b/a ≡ bx ( mod m ) ，则称 x 为 a 模 m 的乘法逆元，记为 $a^{-1}$( mod m ) 或者 inv（ a )。

1.1.3 理解及其相关证明

根据定义：模 m 意义下， a 如果有逆元 x，那么除以 a 相当于乘以 x

b / x1 = b * x1^-1 // 即 b / a = b * a^-1 ,基础乘除转换 inv[x1] ≡ x1^-1 ( mod m) // inv[x1] 即为 x1 在模 m 情况下的逆元 b / x1 ≡ b * inv[x1] ( mod m ) // 结论 

b / x1 ≡ b * inv[x1] ( mod m ) 等式成立证明：（ inv[ x1 ] = x , 即 x1 的逆元为 x）

假设： b1 / x1 mod m = n (式子一) (式子一两边同时乘上 x1) b1 mod m = n * x1 mod m (式子二) (简化式子二) b1 ≡ n * x1 ( mod m ) (式子三) (式子三两边同时乘上 x, x 为 1 / x1, 即假设 x 为 x1 的逆元) (根据定义式) x * x1 ≡ 1 ( mod m ) (式子四 ，因为 x 是 x1 的逆元，所以得出这个式子) b1 * x ≡ n * x1 * x ( mod m ) (式子三等式两边乘以 x -> 式子五) (式子四带入式子五，有) b1 * x ≡ n * 1 ( mod m ) (式子六) (式子六化简) b1 * x ≡ n ( mod m ) (式子七) (与式子七变形) b1 * x mod m = n mod m (式子七) (式子一带入式子七) b1 * x mod m = b1 / x1 mod m mod m (式子八) (等式右边模了一次 m 之后，值肯定比 m 小，因此第二次模 m 无意义，式子八简化) b1 * x mod m = b1 / x1 mod m (结论) (x 是 x1 的逆元，式子三定义的) (证毕) 

$注意$

① 当且仅当 a 与 m 互质时，a 关于 1 模 m 的 乘法逆元 有解。特别地，当模数 m 为质数时，$a^{m-2}$ 即为 a 的乘法逆元。若不互质，则无解。

② 若 m 为素数，则从 1 到 m-1 的任意数都与 m 互质，即在 1 到 m-1 之间都恰好有一个关于 1 模 m 的乘法逆元。

$Q:$ 为什么当 a 与 m 互质时，a 关于 1 模 m 的 乘法逆元 才有解 ???

首先介绍一下 裴蜀定理：

$裴蜀定理$
① 若 a, b 是整数,且 gcd(a , b) = d，那么对于任意的整数 x , y。ax+by 都一定是 d 的倍数，特别地，一定存在整数x,y，使 ax+by = d成立。

② 推论：a ，b 互质的充分必要条件是存在整数 x ， y 使得 ax+by = 1 。

我们可以知道

​ a ⋅ x ≡ 1（ mod m）

⇔ a ⋅ x= 1−my

⇔ ax + my= 1 $（1）$

裴蜀定理告诉我们，方程（1）当且仅当 gcd( a ，m) = 1时有解。也就是说，当且仅当 a 与 模数m 互质时，存在 a 的乘法逆元。因此 大部分 有理数取模问题给定的模数都是质数，这样能够在 a mod m ≠ 0 的情况下保证存在 a 的逆元。

$Q:$ 为什么当模数 m 为质数时，$a^{m-2}$ 即为 a 的乘法逆元 ???

由费马小定理可知：

当 m为质数时，$a^{m-1}$ ≡ 1 ( mod m )

​ ⇒ a * $a^{m-2}$ ≡ 1 ( mod m )

则由逆元定义可知，此时 $a^{m-2}$为 a 的乘法逆元

2. 逆元的四大求解法

2.1 费马小定理求逆元

2.1.1 何为费马小定理

费马小定理是数论中一个定理：

假如 a 是 一个整数，m 是一个质数，那么

​ $a^m$ ≡ a ( mod m )

如果 m 是一个质数，而整数 a 不是 m 的倍数，那么

​ $a^{m-1}$ ≡ 1 ( mod m )

2.1.2 证明费马小定理

下面的证明，使用模运算，最初是由 James Ivory 在1806年发现的，后来被 Dirichlet 在1828年重新发现。

我们首先考虑整数a，2a，3a，…（ p – 1 )a。这些数都不等于p对其他数的模，也不等于0。

如果这样，那么有：r × a ≡ s × a （ mod p ），1 ≤ r < s ≤ p – 1，那么，两边消去a将得到

r ≡ s ( mod p )，这是不可能的，因为 r 和 s 都在 1 和 p – 1 之间。

因此，前一组整数必须同余模 p 到1，2，…p – 1。

把这些同余相乘，你会发现：a × 2a × 3a × … × (p – 1) × a ≡ 1 × 2 × 3 × … × (p – 1) ( mod p)意味着a × （p – 1）! ≡ （p – 1）!（mod p）。

从这个表达式的两边消去（p – 1）!，我们便得到：$a^{p-1}$ ≡ 1 ( mod p )。

2.1.3 代码板子

首先翻出我们之前准备好的结论： b / x1 mod m = b * x mod m (x 是 x1 在模 m 下的逆元) (式子一) 逆元定义： x1 * x ≡ 1 ( mod m ) (式子二) 我们把费马小定理的结论带入式子二,有 x1 * x = x1^(p-1) (式子三) 故此 x = x1^(p-2) (结论) ( 即 x1的 逆元 x 为 x1^(p-2) ) 

/* 快速幂· 求 a^k % m */ /* 求逆元 即为 quick_power( a , m-2 , m ) */ int quick_power(int a,int k,int m) { 
                int res=1; while(k) { 
                if(k&1) res= res*a % m; a= a*a % m; k>>=1; } return res; } 

$费马小定理局限性$

必须满足 m 要为质数 的前提条件 ，才可求逆元

2.2 扩展欧几里得求逆元

2.2.1 何为欧几里得算法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。

公式 ：gcd( a，b ) = gcd( b，a mod b )

2.2.2 证明欧几里得算法

2.2.3 扩展欧几里得算法

由名字可知这是建立在欧几里得算法上的一种算法，定义如下：

​ 给一个线性方程 ax + by = m，给出 a，b，m 求解出相应的 x 和 y 。

$注意$

首先，只有 m % gcd( a，b) ==0 ，即 当且仅当 m 是 a，b 最大公约数的倍数时，该线性方程才有解。

当 m 为1 时，由裴蜀定理推论可知，只有当 a，b互质才有解。

2.2.4 推导扩展欧几里得算法

证：存在整数对( x，y )使得 ax + by = gcd( a，b )

 证明： 设 a > b 当 b = 0 时，a∗1+b∗0 = gcd( a，b ) = a，此时 x=1，y=0 当 b !=0 时， 设 a∗x1 + b∗y1 = gcd( a，b ) b∗x2 + a%b∗y2 = gcd( b，a%b ) 又由于gcd(a,b)=gcd( b，a%b ) 所以有 a∗x1 + b∗y1=b∗x2 + a%b∗y2 又因为 a%b = a − ( a / b )∗b ， 得到 a∗x1 + b∗y1=a∗y2 + b∗x2 − ( a / b )∗b∗y2 ​ 即 x1=y2 ​ y1=x2 − (a/b)∗y2 

2.2.5 代码板子

int exgcd( int a , int b , int &x , int &y ) { 
                     if( !b ) // 当 b =0 时 { 
                     x=1,y=0; return a; } // 当 b！=0 时 int d=exgcd( b, a%b, x, y ); int t=x; x=y; y=t-(a/b)*y; return d; } 

怎么用拓展欧几里得求逆元呢？

把 ax ≡ 1（ mod m）称为 a 关于 1 mod m 的乘法逆元。 它的解其实就相当于寻找方程 ax+my=1 的解。根据乘法逆元的性质，只有当 a 与 m 互质，a 关于模 m 的乘法逆元才有解。如果不互质，则无解。那么这个方程就是 a,m 互质的充要条件是方程 ax+my = 1 必有整数解。

$注意$

我们知道了线性方程 ax + by = m 有整数解的条件，并且根据上述算法，也能求出一组方程的解。但是 这组解很可能包含负数，当我们求逆元时需将其转化为正数，如下

/* 求逆元 a , m */ int Inv_a(int a,int m) { 
                     int x,int y; int d=exgcd(a,m,x,y); if(d==1) { 
                     return ( x%m + m )%m; // 保证逆元为正数 } else return -1; // ax+my=1 不成立，即 a ，m 不互质，无解 } 

2.3 线性递推求逆元

2.3.1 何为线性递推

exgcd和费马小定理只适合用来求单个逆元，求3e6以内所有的逆元在肯定会超时，此时用线性递推求逆元可以保证时间复杂度在O( n )内

2.3.2 推导线性递推

设 t = m / i，k = m % i，有：m = i * t + k 即 i * t + k Ξ 0 ( mod m ) 即 k Ξ - i * t ( mod m ) 两边同时除以 i * k 有 1 / i Ξ - t / k ( mod m ) 将k，t带入 有 inv[ i ] Ξ - m / i * inv[ m % i ] ( mod m ) 为防止有负数，有inv[ i ] = ( m - m / i) * inv[ m % i ]) % m 

核心：inv[ i ] = ( m – m / i ) * inv[ m % i ] % m

2.3.3 代码板子

long long inv[N]; void get_inv( long long m ) { 
                          inv[1]=1; for(int i=2;i<=m-1;i++) inv[i]=( m-m/i )*inv[ m%i ]%m; } 

2.4 欧拉定理求逆元

2.4.1 何为欧拉定理

若a、m互质，则有 $a^{\phi (m)}$ ≡ 1 ( mod m ) ，φ( m)称为欧拉函数，表示1~m中与 m互质的个数

2.4.2 证明欧拉定理

欧拉定理证明

把不超过𝑚且与𝑚互质的正整数拿出来构成集合{ $x_1,x_2,\dots ,x_{\phi (m)}$}

设𝑎与𝑚互质且xi也与m互质，则( $a_{xi}$，m )=(m，$a_{xi}$%m) =1

集合{ $a{x}_1,a{x}_2,\dots ,a{x}_{\phi (m)}$}在模𝑚意义下与前一集合相等 ( 都是与m互质的集合 ）（均为模m意义下模𝑚意义下的缩系）

证毕

2.4.3 推导欧拉函数

$欧拉函数$

ϕ( m ) 为正整数 m 与1，2，⋅⋅⋅，m−1，m互质的个数

设 m = $p^{a1}{p}^{a2}\cdot \cdot \cdot \cdot p^{ak}$

则 ϕ( m ) = $(p_1-1)p_1^{a1-1}\times (p_2-1)p_2^{a2-2}\cdot \cdot \cdot \times (p_k-1)p_k^{ak-1}$

取自[逆元、欧拉定理 – I_N_V – 博客园 (cnblogs.com)]

2.4.4 代码板子

int phi(int x) { 
                                int ans=x; for( int i=2 ; i*i<=x ; i++ )// 时间复杂度：O ( √n ) if(x%i==0) { 
                                ans = ans/i*(i-1); // 由 Φ（m）=m(1- 1 / pi)..得出  while(x%i==0) x/=i;// 除干净质因子 } if(x>1) ans=ans/x*(x-1);// m有一个大于√m 的质数 return ans; } 

3. 阶乘逆元

顾名思义，就是阶层的逆元，即分母，既然这篇文章主要是以逆元为主题，那么顺道提一下，希望有助于排列组合的计算，上板子！！

// 阶乘逆元 typedef long long LL; const int N=1e6+5; LL fac[N]; //阶乘 LL inv[N]; //逆元  // 求阶乘 void get_fac() { 
                                    fac[0] = inv[0] = 1; for (int i = 1 ; i <=  ; i++) { 
                                    fac[i] = fac[i-1] * i % m; inv[i] = quick_power(fac[i],m-2,m); //表示i的阶乘的逆元  } } // 求组合数 inline LL get_C( LL a, LL b ) // C(a,b) = a!/((a-b)!*b!) % mod { 
                                    return fac[a] * inv[a-b] % m * inv[b] % m; } 

以上内容尚未完全，随着今后学习的推进，我会继续对其进行补充与完善。另外，大家如果觉得我写的还行的话，还请赠予我一个可爱的赞，你的赞对于我是莫大的支持。