【数学】模下乘法逆元和快速幂

2021-06-28 约 1093 字预计阅读 3 分钟

乘法逆元介绍

乘法逆元的定义

设模数为 $m$（如常用的模数 $m=10^9+7$），对于一个整数 $a$，如果存在另一个整数 $a^{-1}~(0 < a^{-1} < m)$，满足 $$ a a^{-1} \equiv 1 ~ (\bmod ~ m) $$ 那么我们称 $a^{-1}$是 $a$ 的**「乘法逆元」**（也被称为模逆元或模反元素）。

为什么需要乘法逆元？

乘法逆元可以使得我们在取模的意义下，化除法为乘法。例如当我们需要求出$ \dfrac{b}{a} $对 $m$ 取模的结果，那么可以使用乘法逆元转换为： $$ \frac{b}{a} \equiv b⋅a^{−1}(\bmod m) $$ 来帮助我们求解。因为乘法在取模的意义下满足分配律，即： $$ (a×b)\bmod m=((a \bmod m)×(b \bmod m))\bmod m $$ 但除法在取模的意义下并不满足分配率。因此，当$a$或$b$的求解过程中本身就包含取模运算时，使用乘法逆元，我们仍然可以得到正确的$ \dfrac{b}{a} $对 $m$ 取模的结果。

乘法逆元计算

对于某个数$a$，要获得模$m$下的乘法逆元$a^{-1}~(0 < a^{-1} < m)$，使得$a a^{-1} \equiv 1 ~ (\bmod ~ m)$:

当$m$是$a$的约数时，$a=km$，此时显然不存在满足条件的$a^{-1}$
当$m$不是$a$的约数时：
- 若$m$为质数，则此时$a$和$m$互质。由贝祖定理可得，一定存在整数$x,y$，使$ax+my\equiv1$，即$a^{-1}$存在。
  
  求解$a^{-1}$可以使用费马小定理 ，即 $$ a^{m−1}\equiv 1 (\bmod m) $$ 那么有 $$ a^{m−1}a^{−1} \equiv a^{−1} (\bmod m) $$ $$ a^{m−2}aa^{−1} \equiv a^{−1} (\bmod m) $$ $$ a^{m−2} \equiv a^{−1} (\bmod m) $$ 因此，$m$为质数时，$a^{-1}$就等于$a^{m-2}$对 $m$取模的结果。
  
  计算 $a^{m-2}$的方法相对简单，我们可以使用**「快速幂」**，时间复杂度为 $O(\log m)$
- 若$m$不是质数 ，因为$m$不是质数，$a$和$m$不一定互质。若$a$和$m$不互质，无法求出乘法逆元。
  
  若存在乘法逆元$a^{-1}$，可以使用扩展欧几里得算法 求出。 $$ aa^{−1} \equiv 1 (\bmod m) $$ $$ aa^{-1}+km \equiv 1 $$ 即使用扩展欧几里得算法求$ax+my \equiv 1$的一个整数特解$(x_0,y_0)$，其中$0 < x_0 < m$，就是$a^{-1}$。

1. 模数$m$为质数：使用费马小定理和快速幂

# 使用这种方法时，模数mod必须是质数
mod = 10**9+7
# 模下快速幂
def quickPow(x, n):
    res, cur = 1, x
    while n:
        if n & 1:
            res = (res*cur) % mod
        cur = cur*cur % mod
        n >>= 1
    return res
# mod下的乘法逆元
def inv(num):
    return quickPow(num, mod-2)

2. 模数$m$为任意正整数：使用扩展欧几里得算法

# 模数mod，可以不是质数
mod = 10**9
# 扩展欧几里得算法
def exEuclid(a, b) -> Tuple:
    (a, b) = (a, b) if a >= b else (b, a)
    if b == 0 or a % b == 0:
        return (0, 1, b)
    (x1, y1, gcd) = exEuclid(b, a % b)
    x0, y0 = y1, x1-(a//b)*y1
    return (x0, y0, gcd)
# mod下的乘法逆元，逆元不一定存在
def inv(num):
    _, x, gcd = exEuclid(mod, num % mod)
    return x % mod if gcd == 1 else None

目录