乘法逆元（inverse element）及四大相关求法详解（含证明）-Toy模板网

这篇具有很好参考价值的文章主要介绍了乘法逆元（inverse element）及四大相关求法详解（含证明）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

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

开胃菜

先呈上菜：

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

很明显，上述式子只有一条不成立，即 ( 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 的逆元，式子三定义的)
(证毕)

$\color{orange}注意$

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

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

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

首先介绍一下 裴蜀定理：

$\color{orange}裴蜀定理$
① 若 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 的逆元。

$\color{Red}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;
}

$\color{Green}费马小定理局限性$

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

2.2 扩展欧几里得求逆元

2.2.1 何为欧几里得算法

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

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

2.2.2 证明欧几里得算法

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

2.2.3 扩展欧几里得算法

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

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

$\color{orange}注意$

首先，只有 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

因此可以递归的定义exgcd，同样b=0时递归结束。返回最大公约数。

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 必有整数解。

$\color{orange}注意$

我们知道了线性方程 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^{φ( m)}$ ≡ 1 ( mod m ) ，φ( m)称为欧拉函数，表示1~m中与 m互质的个数

2.4.2 证明欧拉定理

欧拉定理证明

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

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

集合{ $ax_1,ax_2,…,ax_{φ(m)}$ }在模𝑚意义下与前一集合相等 ( 都是与m互质的集合）（均为模m意义下模𝑚意义下的缩系）

将集合内所有原数相乘，得到
$ax_1,ax_2,…,ax_{φ(m)}$ ≡ $a^{φ(m)}∏^{ϕ(m)}_ixi≡∏^{ϕ(m)}_ixi$ ( mod m )
因为 xi 与 m 互质，则都有逆元

对上个式子的右边2个式子每个 xi 都乘上逆元
则 $a^{φ(m)}$ ≡ 1 ( mod m )

证毕

2.4.3 推导欧拉函数

$\color{orange}欧拉函数$

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

设 m = $p^{a1}p^{a2}⋅⋅⋅⋅p^{ak}$

则 ϕ( m ) = $p_1−1)p_1^{a1−1}×(p_2−1)p_2^{a2−2}⋅⋅⋅×(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 <= 1000000 ; 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;
}