逆元反转公式
Published:
引理内容
这个公式似乎没有名字，我个人喜欢叫它逆元反转公式。
$\forall a, b > 1$ 且 $a \perp b$：
\[\text{inv}(a,b) = b - \frac {b \times \text{inv}(b,a) - 1} a\]其中 $\text{inv}(a,b)$ 指的是值域在 $[1,b)$ 中的 $a$ 的唯一模 $b$ 意义下乘法逆元。
$b \times \text{inv}(b,a) \equiv 1 \pmod a$，因此存在整数 $t$ 使得 $t = \frac {b \times \text{inv}(b,a) - 1} a$。
看看怎么通过 $t$ 构造 $\text{inv}(a, b)$，我们尝试看看 $(a \times t) \bmod b$ 的值，发现是 $-1$。因此 $-t$ 是一个逆元。接下来研究 $t$ 的值域。
$t$ 最小是 $\frac {b-1} a \ge 1$；$t$ 最大是 $\frac {b (a-1) - 1} a = b - \frac {b-1} a \le b-1$。即 $t \in [1,b)$。
$-t \in (-b,-1]$，$b-t \in (0,b-1] = [1,b)$。不难发现，$b-t$ 就是 $\text{inv}(a,b)$ 的值，证毕。
功能
- 首先是逆元反转。$a^{-1} \bmod b$ 不好处理的时候，可以反一下看看 $b^{-1} \bmod a$ 好不好。一般搭配题目特殊性质。
- 其次，很多时候我们天然关注逆元在群上的性质（即我们关心的是逆元等价类），而到了需要使用具体数值大小的时候就不太方便。这个公式限制了计算出的逆元大小。
例题
2022 AMC12B Problem 23
有一个无穷长 01 数组 $x$，你不知道它的值。
有一个数列 $S_0 = x_0$，$S_n = S_{n-1} + x_n 2^n$。
已知 $\forall n \ge 1$ 有 $7 S_n \equiv 1 \pmod {2^n}$。
求
\[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}\]
看一下要求的东西，是 $\frac 1 {2^{2019}} (S_{2022} - S_{2018})$。
对于 $n \ge 1$ 有 $S_n \equiv \frac 1 7 \pmod {2^n}$，减掉 $x_n 2^n$ 即 $S_{n-1} \equiv \frac 1 7 \pmod {2^n}$。注意到 $S_{n-1} < 2^n$，因此 $S_{n-1} = \text{inv}(7, 2^n)$。
逆元反转：
\[S_{n-1} = \text{inv}(7, 2^n) = 2^n - \frac {2^n \text{inv}(2^n, 7) - 1} 7 = 2^n - \frac {2^n (4^n \bmod 7) - 1} 7\]通项公式有了，后面就是简单体力活了。$4^n \bmod 7 = 4^{n \bmod 6} \bmod 7$ 加速计算。答案是 $\boxed{6}$。
2023 AIME II Problem 15
对于正整数 $n$，定义 $a_n$ 为满足 $a_n \equiv 1 \pmod {2^n}$ 的最小正整数。
求 $n \in [1,1000]$ 中有几个 $n$ 满足 $a_n = a_{n+1}$。
设 $a_n = 23 b_n$，那么 $b_n = \text{inv}(23, 2^n)$。然后我们就不管 $a_n$ 了，$a_n = a_{n+1}$ 等价于 $b_n = b_{n+1}$。
逆元反转：
\[b_n = \text{inv}(23, 2^n) = 2^n - \frac {2^n \text{inv}(2^n, 23) - 1} {23} = 2^n - \frac {2^n (12^n \bmod 23) - 1} {23}\]只有 $\text{ord}(2,23) = 11$ 种可能。
那么暴力计算打出 $n = 0$ 到 $n = 11$ 的 $b_n$ 的表：
\[b_{[0,11]} = \langle 1, 1, 3, 7, 7, 7, 39, 39, 167, 423, 935, 1959 \rangle\]观察其中 $n=0$ 到 $n=10$ 的部分，由周期性可知，在 $n \bmod 11 \in {0, 3, 4, 6}$ 时，$b_n = b_{n+1}$。
后面简单了，$1000 = 90 \times 11 + 10$，答案 $\boxed{363}$。