逆元

模逆元的形式化定义

设 a 为整数，m 为正整数。如果存在一个整数 x，使得

ax ≡ 1 (mod m)

则称整数 x 是 a 模 m 的模逆元，记作 a ^ {-1} (mod m)

案例：求 3 ^ {-1} (mod 7)

我们需要寻找一个 x，满足 3 * x ≡ 1 (mod 7)

最后求出 x = 5

逆元存在性定理

a 模 m 的逆元 a ^ {-1} (mod m) 存在的充要条件是 a 与 m 互素，即

gcd(a,m) = 1

扩展欧几里得算法

当模数 m 非常巨大时，我们不可能像前面那样用穷举法去试出逆元。我们需要高效的算法——扩展欧几里得算法

对任意正整数 a 和 b，必然存在整数 x 和 y，使得

ax + by = gcd(a, b)

特别地，当 gcd(a, m) = 1 时，方程 ax + my = 1 必然有整数解

当我们让方程 ax + my = 1 的两边同时对 m 取模

ax + my ≡ 1 (mod m)

由于 my 是 m 的倍数，在模 m 意义下 my ≡ 0，方程瞬间简化为

ax ≡ 1 (mod m)