模反元素 | Ray's Blog

又稱模倒數、模逆元，簡稱$MMI$或$inv$

如果$a$跟$n$互質

那一定有一個$b$，讓$(a \times b) \mod n = 1$
或$(a \times b - 1)$可以整除$n$

這時候$b$就是$a \mod n$的模反元素

而且$b + kn, k \in Z$
$b + kn$都是$a \mod n$的模反元素

用途

在求$a \div b \mod p$時，如果$a$、$b$太大無法直接相除

需要把$\div b$替換成$\times c$，並使$a \div b \equiv a \times c \pmod p$

這樣就可以拆成$(a \mod p) \times (c \mod p)$
而這個$c$就是模反元素

處理溢位時尤為好用

$3$、$11$互質
$inv = 4$
$3 \times 4 \mod 11 = 1$

所以根據定義：
$4 + 11k = 4, 15, 26 ...$
$3 \times 15 \mod 11 = 1$
$3 \times 26 \mod 11 = 1$
$...$
$3 \times (4 + 11k) \mod 11 = 1, k \in Z$

那怎麼知道$b$，或者說是$inv$?

#define MOD 1000000007

ll inv(ll a) {
    return qpow(a, MOD - 2);
}

inv(n); // 即為模反元素

$MOD$必須為質數

舉例：

#define MOD 11

int main() {
    cout << inv(3, MOD); // 4
}

首先根據貝祖等式，可以用擴展歐幾里得算法找到整數$x$、$y$符合：
$ax + by = gcd(a, b)$

貝祖定理中有說：
如果整數$a$、$b$互質，那$ax + by = 1$的$x$、$y$有整數解

我們知道$MOD$(以下為$M$)是質數，所以

$gcd(a, M) = 1$
$ax + My = gcd(a, M) = 1$

此時$x$、$y$必定有整數解

整個算式取模

$(ax + My) \mod M = (1) \mod M$
$ax \mod M = 1$

那$x$就是我們要找的模反元素

如果$a$是一個整數，$p$是一個質數
那$a^p \equiv a \pmod p$

而且$a^{p-1} \equiv 1 \pmod p$
整個同乘$a^{-1}$，所以$a^{p-2} \equiv a^{-1} \pmod p$
反過來看$a^{-1} \equiv a^{p-2} \pmod p$

套到之前的質數$M$中：
$a^{-1} \equiv a^{M-2} \pmod M$

同等於：
$a^{-1} \mod M = a^{M-2} \mod M$

上面說過：
$ax \mod M = 1$
所以同除以 $a$ 後：
$x \mod M = \frac{1}{a} = a^{-1}$

且$a^{-1} \mod M = a^{M-2} \mod M$

所以$x = a^{M-2} \mod M$