$a,b\in\mathbb{Z}$,且 $ab \equiv 1 \pmod{n}$,则称 $a$ 和 $b$ 关于模 $n$ 互为模逆元(Modular Multiplicative Inverse)

还可记作:$b \equiv \frac{1}{a} \pmod{n}$ 或 $b \equiv a^{-1} \pmod{n}$

模运算的部分性质

$(a+b)\bmod n=(a\bmod n+b\bmod n)\bmod n$

$(a-b)\bmod n=(a\bmod n-b\bmod n+n)\bmod n$

$(a\cdot b)\bmod n=((a\bmod n)\cdot (b\bmod n))\bmod n$

$a^b\bmod n=(a\bmod n)^b\bmod n$

上面三条性质,相当于加、减、乘、乘方都齐了,那么除呢?$\frac{a}{b}\bmod n=\ ?$

这就需要模逆元来解决。

模逆元

类比倒数 $a\cdot b=1$, $ab \equiv 1 \pmod{n}$ 也可以称它们互为模倒数(模逆元)

那么如果知道 $b$ 的模逆元为 $x$, $\frac{a}{b}\bmod c$ 就可以转化为 $(a\cdot x) \bmod c$

求法

费马小定理 (Fermat's Little Theorem)

若 $p$ 为质数,整数 $a$ 与 $p$ 互质,则 $a^{p-1}\equiv 1\pmod p$

另一种形式:对于任意整数 $a$,有 $a^p\equiv a\pmod p$

由以上定理:

$a^{p-1}\equiv 1\pmod p$

左边提出一个 $a$:

$a\cdot a^{p-2}\equiv 1\pmod p$

因此可得出:

$a^{-1}\equiv a^{p-2}\pmod p$

因此 $a$ 关于模 $p$ 的逆元就是 $a^{p-2}\bmod p$。

例如要求 $(15/5)\bmod 4$,就先求 $5$ 关于 $4$ 的逆元 $5^{4-2}\bmod 4=25\bmod 4=1$,然后就可以转化为 $(15/5)\bmod 4=(15\cdot 1)\bmod 4=3$

快速幂

在实际题目中,模 $p$ 往往非常大,比如为 $20220211$,那要求一个数的模逆元就会进行一个很大指数运算,因此为了节省时间需要使用快速幂。同时快速幂也兼容取模,因此可以在算幂的同时进行取模运算。

#define MOD 20220211
long long fastpow(long long a, long long b)
{
    a %= MOD; // 开头先取一次模
    long long ans = 1;
    while (b)
    {
        if (b % 2 == 1)
            ans = ans * a % MOD; // 每次运算都取模
        a = a * a % MOD; // 每次运算都取模
        b >>= 1;
    }
    return ans;
}

标签: 逆元

添加新评论