乘法逆元 | 山暮云秋

乘法逆元介绍

引入

1、对于模意义下的运算，例如我们知道有 $(a + b) \bmod p = (a \bmod p) + (b \bmod p)$ 或者 $(a * b) \bmod p = (a \bmod p) * (b \bmod p)$ 成立，但是对于模意义下的除法却不成立：$(a / b) \bmod p \not= (a \bmod p) / (b \bmod p)$ 。不过，我们可以把模意义的除法转换成模意义的乘法
2、举例探讨：$(7 / 2) \bmod 5$ 中，把除法转成乘法写作 $(7 * \frac{1}{2}) \bmod 5$ ，再将分数写成幂的形式写作 $(7 * 2^{-1}) \bmod 5$
3、由于取模运算的结果一定是整数，所以 $(7 * 2^{-1}) \bmod 5$ 结果一定是整数，即说明必定能把 $2^{-1}$ 这个分数转换成某个整数。所以，问题的关键就在于能转换成哪个整数
4、这时便需要引入乘法逆元的概念了，它可以辅助我们完成模意义的除法到模意义的乘法的转换

简单介绍

1、类比初中的倒数的概念：如果 $a * b = 1$，则 $a$ 和 $b$ 互为倒数。对于 $(7 * 2^{-1}) \bmod 5$ 来说，其可以等价地写成 $(7 * 3) \bmod 5$，这是因为在 $\pmod 5$ 下，有 $(3 * 2) \bmod 5 = 1$ 成立。可以近似地理解成，$3$ 和 $2$ 在 $\pmod 5$ 下互为倒数，但这里实际不称作倒数，而称作乘法逆元
2、因此，对于上面的例子，$(7 * \frac{1}{2}) \bmod 5$ ，就可以理解成 $(7 * (2\ 的乘法逆元)) \bmod 5$ ，这样便可以转换成模意义的乘法得到结果。即被除数除以除数再 $\bmod \ n$，等同于被除数乘除数的乘法逆元再 $\bmod \ n$
3、如何得到乘法逆元？例如求 $\frac{1}{2}$ 在 $\pmod 7$ 下的乘法逆元，就要看 $谁 * 2 \bmod 7 = 1$，显然存在 $(2 * 4) \bmod 7 = 1$，因此 $4$ 是 $\frac{1}{2}$ 在 $\pmod 7$ 下的乘法逆元 ，算式写作 $2^{-1} \bmod 7 = 4$。注意此时式子中 $2^{-1}$ 代表逆元，而不是分数
4、上面是对乘法逆元的简单介绍，下面将从数学角度(同余方程)给出乘法逆元的详细定义、自身性质、运算性质等内容
乘法逆元

1、定义：设 $a \in Z, n \in N$，如果有 $az \equiv 1 \pmod n$ 存在(同余方程)，则称 $z$ 是 $a$ 在 $\pmod n$ 下的乘法逆元，记作 $a^{-1} = z \pmod n$。注意其中 $a^{-1}$ 应理解为逆元而非幂
2、性质：$a$ 的乘法逆元 $a^{-1} = z$，那么 $z$ 的乘法逆元 $z^{-1} = {(a^{-1})}^{-1} = a$，则说明一个数的逆元的逆元是它本身
3、运算：
$$\begin{aligned} &(3^{-8} \times 3^{5}) &\mod 5 \\ =\ &3^{-3} &\mod 5 &\quad\text{幂运算的性质} \\ =\ &{(3^{-1})}^3 &\mod 5 \\ =\ &2^3 &\mod 5 &\quad\text{求逆元:} \ 3^{-1} = 2 \pmod 5 \\ =\ &3 \end{aligned} $$
注意事项

1、在 $\pmod n$ 下互为乘法逆元，一般只考虑比 $n$ 小的。例如 $2^{-1} = 3 \pmod 5$ 而不是 $2^{-1} = 8 \pmod 5$，因为 $3 \lt 5$ 而 $8 \gt 5$
2、$a$ 在 $\pmod n$ 下的乘法逆元 $a^{-1}$ 是唯一的。例如 $2 \times 3 \equiv 1 \pmod 5$，则 $2,3$ 再没有其他的逆元了
3、乘法逆元存在的条件：只有当一个整数与模数互素—— $gcd(a,n) = 1$ 时，它才有相应的乘法逆元

求逆元-拓展欧几里得算法

引入

1、由于前面乘法逆元性质中提到，只有当 $gcd(a, n) = 1$ (即 $a, n$ 互素，$n$ 为模数)才有乘法逆元存在。先前介绍过拓展欧几里得算法，因为 $gcd(a, n) = 1$ ，根据裴蜀定理一定有 $as + nt = gcd(a, n) = 1$ ，等式两边同时 $\bmod \ 5$，便得到 $as \equiv 1 \pmod n$ ，易知 $a$ 的乘法逆元 $a^{-1} = s \pmod n$
2、因此，要求乘法逆元时，就可以调用拓展欧几里得算法，把 $a, n$ 当做参数传入，其返回的 $s$ 即为所求
3、对于下面代码，要得到最小的正整数的乘法逆元 $inv_b$，只需要处理一下 $s$：$inv_b = (s \bmod n + n) \bmod n$

代码实现

#include <iostream>
using namespace std;

int ex_gcd(int a, int b, int &s, int &t)
{
    // s, t 表示 s_i 和 t_i，其默认值为 s_1 = 0 和 t_1 = 1
    // s_ 和 t_ 表示 s_i-1 和 t_i-1，其默认值表示 s_0 = 1 和 t_0 = 0
    int s_ = 1, t_ = 0, q, temp;
    while (a % b)
    {
        q = a / b;

        // 迭代公式：s_i+1 = s_i-1 - s_i * q_i
        temp = s;       // 记录当前 s_i
        s = s_ - s * q; // 计算 s_i+1
        s_ = temp;      // 下一轮 s_i
        // 迭代公式计算 t_i+1
        temp = t;
        t = t_ - t * q;
        t_ = temp;

        temp = a % b;
        a = b;
        b = temp;
    }
    return b;
}

int main()
{
    // 求 (a / b) % n 的值，易证 s 为 b 的乘法逆元
    // s, t 表示 s_i 和 t_i，其默认值为 s_1 = 0 和 t_1 = 1
    int a, b, n, s = 0, t = 1;
    cin >> a >> b >> n;

    // 如果 b, n 互素，才有乘法逆元；算出 b 的乘法逆元，存入 s
    if (ex_gcd(b, n, s, t) == 1)
    {
        // 得到最小的正整数的乘法逆元
        int inv_b = (s % n + n) % n;
        // 被除数 除以 除数 再模 n，等同于 被除数 乘 除数的乘法逆元 再模 n
        // 对于模乘法，(a * b) % n = ((a % n) * (b % n)) % n
        cout << ((a % n) * (inv_b % n)) % n;
    }
    else
        cout << "Impossible";
    return 0;
}

求逆元-快速幂 & 费马小定理

引入

1、费马小定理：若有整数 $a, p$ 且 $p$ 为质数，则有 $(a^p - a)$ 是 $p$ 的倍数，也可以表示为 $a^p \equiv a \pmod p$。如果 $a$ 不是 $p$ 的倍数的话，这个定理可描述为 $a^{p-1} \equiv 1 \pmod p$
2、因为乘法逆元性质有 $gcd(a, n) = 1$ ($a, n$ 互素，$n$ 为模数)，满足 $a$ 不是 $n$ 的倍数。因此，当 $n$ 为质数时(必须条件)，一定有 $a^{n-1} \equiv 1 \pmod n$。又因为乘法逆元定义中有 $az \equiv 1 \pmod n$ 时 $z$ 为 $a$ 的乘法逆元，因此得到 $az \equiv a^{n-1} \pmod n$。两边同除 $a$，得到 $z \equiv a^{n-2} \pmod n$
3、因此，在 $n$ 为质数的情况下($10^9 + 7$ 是常见的满足条件的模数)，要求乘法逆元 $z$，只需要求 $a^{n-2} \bmod n$ 的值，使用快速幂(幂取模)来计算即可

代码实现

#include <iostream>
using namespace std;

int gcd(int a, int b)
{
    int temp;
    while (a % b)
    {
        temp = a;
        a = b;
        b = temp % b;
    }
    return b;
}

// 幂取模
unsigned long long ModExp(int a, int n, int m)
{
    unsigned long long result = 1;
    a %= m; // 对第一次的乘数 a 取模

    while (n)
    {
        if (n & 1)
            result = (result * a) % m; // 对结果取模，结果又是下一次运算的乘数之一

        a = (a * a) % m; // 对乘数 a 取模
        n >>= 1;
    }

    return result;
}

int main()
{
    // 求 (a / b) % n 的值
    int a, b, n;
    cin >> a >> b >> n;

    // 如果 b, n 互素，才有乘法逆元；只有 n 为质数才可以用快速幂(is_prime细节省略)
    if (gcd(b, n) == 1 && is_prime(n))
    {
        // b 的乘法逆元
        int inv_b = ModExp(b, n - 2, n) % n;
        cout << ((a % n) * (inv_b % n)) % n;
    }
    else
        cout << "Impossible";
    return 0;
}

求逆元-线性递推

引入

1、设 $n = aq + r$ ($a, n$ 互素，$n$ 为模数)，必然有 $aq + r \equiv 0 \pmod n$ ，且有 $q = n / a,\ r = n \bmod a$
2、证明：
$$ \begin{aligned} aq + r &\equiv 0 &\pmod n \\ aq(a^{-1}r^{-1}) + r(a^{-1}r^{-1}) &\equiv 0 &\pmod n &\quad\text{两边同乘} (a^{-1}r^{-1}) \\ qr^{-1} + a^{-1} &\equiv 0 &\pmod n &\quad\text{逆元性质} aa^{-1} = 1 \pmod n \\ a^{-1} &\equiv -qr^{-1} &\pmod n &\quad\text{移项} \\ a^{-1} &\equiv -\frac{n}{a}(n \bmod a)^{-1} &\pmod n &\quad\text{带入 } q,r \end{aligned} $$
3、分析可得，同余方程右侧的 $n \bmod a$ 一定小于方程左侧的 $a$ ，这说明如果通过递推的方式求左侧值时，右侧的值都是已知的，只需要给出 $inv[0] = 0$, $inv[1] = 1$ ($0$ 没有乘法逆元，$1$ 的乘法逆元是 $1$)作为递推初始值即可。另外，右侧的 $-\frac{n}{a}$ 使得求得的左侧值可能是负值，因此需要转换成最小的正整数的乘法逆元：$inv[i] = (inv[i] \bmod n + n) % n$
4、因此，要求乘法逆元 $z = a^{-1}$，可以通过递推式 $inv[a] = -n / a * inv[n \bmod a]$ 计算(其中 $inv[0] = 0, inv[1] = 1$ ，注意每次计算后须转换为最小正整数乘法逆元)

代码实现

#include <iostream>
using namespace std;

// inv[0] = 0, inv[1] = 1
int inv[1000001] = {0, 1};

int gcd(int a, int b)
{
    int temp;
    while (a % b)
    {
        temp = a;
        a = b;
        b = temp % b;
    }
    return b;
}

// 转换成最小正整数逆元
int pos_mod(int a, int n)
{
    return (a % n + n) % n;
}

// 递归计算乘法逆元
int get_inv(int a, int n)
{
    // 直到计算到 inv[a]，可能是inv[0] 或 inv[1]
    if (inv[a])
        return inv[a];
    // 递推表达式，未知值继续递归
    inv[a] = pos_mod(-n / a * get_inv(n % a, n), n);

    return inv[a]; // 返回最后的结果
}

int main()
{
    // 求 (a / b) % n 的值
    int a, b, n;
    cin >> a >> b >> n;

    // 如果 b, n 互素，才有乘法逆元
    if (gcd(b, n) == 1)
    {
        int inv_b = get_inv(b, n);
        cout << ((a % n) * (inv_b % n)) % n;
    }
    else
        cout << "Impossible";
    return 0;
}

乘法逆元介绍

求逆元-拓展欧几里得算法

求逆元-快速幂 & 费马小定理

求逆元-线性递推

页底评论