问题引导的数论探究：广义乘法逆元

· · 算法·理论

这是一篇轻松有趣的数论探讨小专栏。标题致敬了朱富海老师的代数学系列。

众所周知，当 a\perp n 时，存在 b 使得 ab\equiv 1\pmod n，这里的 b 被称作 a 的乘法逆元。但是，当 a\not\perp n 时，我们还能否找到满足类似性质的 b 呢？数学之思以穆尔-彭罗斯逆为嚆矢。滥觞于互质限制的框架正悄然消解其桎梏。在天然具有交换禀赋的整数之代数结构上，隐去不必的繁冗约束，广义乘法逆元的定义遂豁然洞开。

定义 1. 对于正整数 a,n，满足 n\nmid a，若存在正整数 b 使得 a^2b\equiv a\pmod n,ab^2\equiv b\pmod n，则称 b 是 a 的广义乘法逆元。

可以发现，在定义中，我们不再要求 ab\equiv 1\pmod n，转而要求多乘一个 a 或 b 的等式成立。正是这种定义让我们可以绕开互质的要求。

问题 a. 是否对于所有的整数对 (a,n)，我都一定存在满足条件的 b 呢？

很可惜，这个想法是错误的。例如当 a=2,n=4 时，如果存在满足条件的 b，就会有 2^2b\equiv 2\pmod 4，结果就是 0\equiv 2\pmod 4，矛盾。因此，我们必须探寻广义乘法逆元存在的充要条件。

问题 b. 广义乘法逆元存在的充要条件是什么？

让我们从定义出发，a^2b\equiv a\pmod n\iff n\mid a(ab-1)，根据整除的性质，这等价于 \frac{n}{\gcd(n,a)}\mid (ab-1)，也就等价于

ab\equiv 1\quad\left(\bmod\ {\frac n{\gcd(n,a)}}\right).\tag 1

那么第一个限制也就被我们转化成了乘法逆元的式子。这是我们比较熟悉的：这个式子有解当且仅当 a\perp \frac{n}{\gcd(n,a)}。

接下来把目光放在第二个限制上，ab^2\equiv b\pmod n\iff n\mid b(ab-1)。因为 b 未知，我们不采用上面的推导方法。而是注意到 b 和 ab-1 是互质的，所以 n 一定可以分成互质的两部分，即 n=xy,x\perp y，且这两部分分别整除 b,ab-1，那么我们就得到了线性同余方程组

\begin{cases}b\equiv 0\pmod x\\ ab\equiv 1\pmod y\end{cases}.\tag{2}

这里面第二个方程有解的前提是 a\perp y。在此前提下，根据中国剩余定理，在 1\sim n 中存在唯一一个正整数 b 满足此方程组。

换言之，对于每个满足 n/y\perp y,a\perp y 的 y，都唯一存在一个 b\in[1,n]\cap \mathbb Z，使其满足 ab^2\equiv b\pmod n。

综合上面的论述，我们得知了若 a 有广义乘法逆元，则必有 a\perp \frac n{\gcd(n,a)}。那么 a\perp \frac n{\gcd(n,a)} 是否能推出 a 有广义乘法逆元呢？

答案是肯定的。首先，我们令 y=\frac n{\gcd(n,a)}，则 n/y=\gcd(n,a) 是 a 的因子，根据 a\perp y，必然有 n/y\perp y。故存在整数 b 满足方程组 (2)。因为此时 (1) 式是方程组 (2) 的第二个方程，所以满足 (2) 的解一定满足 (1) 的解，因此根据 y=n/\gcd(n,a) 时解的存在性即知，存在整数 b 同时满足 a^2b\equiv a\pmod n,ab^2\equiv b\pmod n。

定理 2. 对于正整数 a,n，若 n\nmid a，则在模 n 意义下，a 有广义乘法逆元等价于 a\perp \frac n{\gcd(n,a)}。

问题 c. 若 a 有广义乘法逆元，那么它的广义乘法逆元在模 n 意义下是唯一的吗？

这一点可以很容易地从定义推导出来，让我们先假设 a 有两个广义乘法逆元 b,c，满足 b\not\equiv c\pmod n，则 ab^2\equiv b\pmod n,a^2b\equiv a\pmod n,ac^2\equiv c\pmod n,a^2c\equiv a\pmod n，故有

b\equiv ab^2\equiv a^2cb^2\equiv abc\equiv a^2bc^2\equiv ac^2\equiv c\pmod n.

这就矛盾了！所以广义乘法逆元在在模 n 意义下是唯一的。

定理 3. 对于正整数 a,n，满足 n\nmid a，若 a 有广义乘法逆元，则广义乘法逆元在在模 n 意义下是唯一的。

这样子我们就完全地解决了广义乘法逆元的存在唯一性问题了。

问题 d. 条件 a\perp \frac n{\gcd(n,a)} 究竟是什么意思？

设 n 的质因数分解为 \prod_{i=1}^kp_i^{\alpha_i}，同理设 a=\prod_{i=1}^kp_i^{\beta_i}，这里允许某些 \alpha_i,\beta_i 为 0。则 \gcd(n,a)=\prod_{i=1}^k p_i^{\min(\alpha_i,\beta_i)}，那么 a\perp \frac{n}{\gcd(n,a)} 的意思就是 \forall i,\min(\beta_i,\alpha_i-\min(\alpha_i,\beta_i))=0。分类讨论 \alpha_i,\beta_i 的大小关系就可以知道，这个等式的含义是要么 \beta_i\ge \alpha_i，要么 \beta_i=0。换句话说，如果某个素数 p 同时整除 a,n，则 v_p(a) 必须大于等于 v_p(n)。

事实上，我们有很多等价的条件来刻画 a\perp \frac n{\gcd(n,a)}。例如 \gcd(a,n)=\gcd(a^2,n)，以及 \gcd(a^2,n)\mid a。这些条件与 a\perp \frac n{\gcd(n,a)} 的等价性都可以从我们上面的解读推出。

问题 e. 如果 a\perp \frac n{\gcd(n,a)}，我要怎么设计算法求出 a 的广义乘法逆元呢？

其实这个问题我们前面已经解决得差不多了，在方程组 (2) 中，我们选定 y=\frac n{\gcd(n,a)}，则两个方程的解可以分别解出（第二个方程要用 exgcd 去解），然后再用一次 CRT 就可以得到广义乘法逆元了。时间复杂度为 \mathcal O(\log n)。

问题 f. 如果 a\perp \frac n{\gcd(n,a)}，我能不能用一个具体的表达式表示出广义乘法逆元呢？

我们先回忆一下扩展欧拉定理的内容，若 m\ge \varphi(n)，则

a^m\equiv a^{[m\bmod \varphi(n)]+\varphi(n)}.

即当 m 很大时，a^m\bmod n 会陷入循环。

这个定理和广义乘法逆元有什么关系呢？

回忆前文证明唯一性的过程，我们其实是使用了广义乘法逆元的定义式，先升次、再降次来证明的。而扩展欧拉定理是适合拿来降次的！那么，我们可以考虑先用定义式升次，然后综合利用扩展欧拉定理和定义式降次，也许就会有新的结果出现。

我们先尝试升次操作，b\equiv ab^2\equiv ab(ab^2)\equiv a^2b^3\equiv \cdots\equiv a^mb^{m+1}\pmod n。当 m=k\varphi(n),k\ge 1 时，根据扩展欧拉定理，有

b\equiv a^{k\varphi(n)}b^{k\varphi(n)+1}\equiv a^{k\varphi(n)}b^{\varphi(n)+1}\pmod n.

分别令 k=1,2 有 b\equiv a^{\varphi(n)}b^{\varphi(n)+1}\equiv a^{2\varphi(n)}b^{\varphi(n)+1}\pmod n，所以有

b\equiv a^{\varphi(n)}a^{\varphi(n)}b^{\varphi(n)+1}\equiv a^{\varphi(n)}b\pmod n.

最后再用一次定义式降次即可：b\equiv a^{\varphi(n)-2}a^2b\equiv a^{\varphi(n)-1}\pmod n。这样我们就知道了，其实广义乘法逆元就是 a^{\varphi(n)-1}！

定理 4. 对于正整数 a,n，满足 n\nmid a,a\perp \frac n{\gcd(a,n)}，则 a 的广义乘法逆元是 a^{\varphi(n)-1}。

如果 \varphi(n) 已知，那么这个定理可以帮助我们直接利用快速幂得到答案。

可以发现，乘法逆元的表达式和广义乘法逆元的表达式一模一样。从这个层面上讲，广义乘法逆元的确是乘法逆元的推广。

这个定理的一个小小推论是，如果 a\perp \frac n{\gcd(a,n)}，则 a\equiv a^2b\equiv a^2a^{\varphi(n)-1}\equiv a^{\varphi(n)+1}\pmod n。这相当于是对欧拉定理的推广，它告诉我们当 a\perp \frac n{\gcd(a,n)} 时，a^m\bmod n,m\ge 1 是纯循环的。

推论 5. 对于正整数 a,n，若 a\perp \frac n{\gcd(a,n)}，则 a\equiv a^{\varphi(n)+1}\pmod n。

自然地，我们想探究这个推论的逆命题是否成立。

问题 g. 如果 a\equiv a^{\varphi(n)+1}\pmod n，则是否一定有 a\perp \frac n{\gcd(a,n)}？

答案是，逆命题也是成立的。这是因为当 a\equiv a^{\varphi(n)+1}\pmod n 时，若取 b=a^{\varphi(n)-1}，则 a^2b\equiv a^{\varphi(n)+1}\equiv a\pmod n，且 ab^2\equiv a^{2\varphi(n)-1}\equiv b\pmod n，即此时 a 是有广义乘法逆元的。根据定理 2 就有 a\perp \frac n{\gcd(a,n)}。

定理 6. 对于正整数 a,n，a\perp \frac n{\gcd(a,n)} 等价于 a\equiv a^{\varphi(n)+1}\pmod n。

这上面就是我前一段时间的一些研究了，写的比较详细，也是希望这篇文章能让数论初学者也看懂。在最开始定义广义乘法逆元时，我们为了顺应直觉，限制了 n\nmid a。不过这个限制是可以去掉的，因为我们可以定义 n\mid a 时 a 的广义乘法逆元是 0。容易验证这个定义是符合上述所有定理的。

上文的结论可以总结为以下三点：

1.（存在唯一性）a 在模 n 意义下有广义乘法逆元当且仅当 a\perp \frac n{\gcd(n,a)}，当且仅当 \gcd(a,n)=\gcd(a^2,n)，当且仅当 \gcd(a^2,n)\mid a。且广义乘法逆元在模 n 意义下唯一；

2.（计算方法）若 a 有广义乘法逆元，则存在 \mathcal O(\log n) 的算法将其求出，且可表示为 a^{\varphi(n)+1}；

3.（扩展扩展欧拉定理）a\perp \frac n{\gcd(a,n)} 等价于 a\equiv a^{\varphi(n)+1}\pmod n。