乘法逆元 | 圣奇宝枣的博客小站

乘法逆元介绍

引入

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

乘法逆元

1、类比初中的倒数的概念：如果 a * b = 1，则 a 和 b 互为倒数。对于 (7 * 2^-1) % 5 来说，其可以等价地写成 (7 * 3) % 5，这是因为在模 5 下，有 (3 * 2) % 5 = 1 成立。可以近似地理解成，3 和 2在模 5下互为倒数，但这里实际不称作倒数，而称作乘法逆元
2、因此，对于上面的例子，7 乘 (1/2) 模 5，就可以理解成7 乘 (2 的乘法逆元) 模 5，这样便可以转换成模意义的乘法得到结果。即被除数除以除数再模 n，等同于被除数乘除数的乘法逆元再模 n
3、如何得到乘法逆元？例如求 (1/2) 在模 7 下的乘法逆元，就要看谁乘 2 模 7 等于 1，显然存在 (2 * 4) % 7 = 1，因此4 是 (1/2) 的乘法逆元，算式写作 2^-1 mod 7 = 4。注意此时式子中 2^-1 代表逆元，而不是分数
4、乘法逆元的详细定义如下图。模运算下也会继承一些普通幂运算的性质，如下图的运算示例。乘法逆元还有一些性质，如下图

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

引入

1、由于前面乘法逆元性质中提到，只有当gcd(a, n) = 1(即 a, n 互素，n 为模数)才有乘法逆元存在。先前介绍过拓展欧几里得算法，因为gcd(a, n) = 1，根据裴蜀定理一定有as + nt = gcd(a, n) = 1，等式两边同时模 n，便得到 a*s 和 1 在模 n 下同余。易知，模 n 下 a 的乘法逆元是 s
2、因此，要求乘法逆元时，就可以调用拓展欧几里得算法，把 a, n 当做参数传入，其返回的 s 即为所求。要得到最小的正整数的乘法逆元inv[b]，只需要处理一下 s：inv_b = (s % n + n) % 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 与 a 在模 p 下同余。如果 a 不是 p 的倍数的话，这个定理可描述为 a^p-1 和 1 在模 p 下同余
2、因为乘法逆元性质有gcd(a, n) = 1(a, n 互素，n 为模数)，满足 a 不是 n 的倍数。因此，当 n 为质数时(必须条件)，一定有 a^n-1 和 1 在模 n 下同余，又因为乘法逆元定义中有 a*z 和 1 在模 n 下同余(z 为 a 的乘法逆元)，因此得到 a*z 和 a^n-1 在模 n 下同余。两边同时除以 a，得到 z 和 a^n-2 在模 n 下同余
3、因此，在 n 为质数的情况下(1e9 + 7 是常见的满足条件的模数)，要求乘法逆元 z，只需要求 a^n-2 % 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 = a * q + r(a, n 互素，n 为模数)，必然有 aq + r 与 0 在模 n 下同余，且有q = n / a，r = n % a
2、令同余方程两边同乘 a^-1 * r^-1(即inv[a] * inv[r])，因为乘法逆元定义中有(a * inv[a]) % n = 1，所以方程可变为 q * inv[r] + inv[a] 与 0 在模 n 下同余，移项得到 inv[a] 与 -q * inv[r] 在模 n 下同余。把第一步得到的 q, n 的值带入，最终得到 inv[a] 与 -(n / a) * inv[n % a] 在模 n 下同余
3、分析可得，同余方程右侧的[n % a]一定小于方程左侧的[a]，这说明如果通过递推的方式求左侧值时，右侧的值都是已知的，只需要给出inv[0] = 0, inv[1] = 1(0 没有乘法逆元，1 的乘法逆元是 1)作为递推初始值即可。另外，右侧的有-(n / a)使得求得的左侧值可能是负值，因此需要转换成最小的正整数的乘法逆元：inv = (inv % n + n) % n
4、因此，要求乘法逆元 z(z = inv[a])，可以通过递推式inv[a] = -n / a * inv[n % 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;
}

乘法逆元介绍

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

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

求逆元-线性递推

页底评论