WTF zk 教程第 6 讲：模运算除法

模运算的除法和普通整数的除法有很大区别，理解它非常重要。这一讲，我们将介绍模运算除法，模逆，和计算逆元的方法。

1. 除法

上一讲我们介绍了模运算中的加法和乘法，和普通加法/乘法类似。但模运算的除法和普通除法很不同。如果我们将整数除法运用到模运算中，会产生奇怪的结果。举个例子，我们知道 $6 \equiv 12 \pmod{3}$，如果我们将两边同时除以 3 会得到 $2 \equiv 4 \pmod{3}$，这显然不成立。因此，普通除法行不通，我们必须换个方式定义模运算中的除法。

一般来说，除法是乘法的逆运算，能逆转乘法的效果。比如在模 $n$ 下， 如果有 $xy \equiv z$，那么 $z/y$ 的结果应该为 $x$。换句话说，在模运算中，计算 $z$ 除以 $y$ 其实是寻找使得 $xy \equiv z$ 成立的整数 $x$ 。

举个例子，计算 $4/2 \mod 5$，我们可以通过穷举法找到 $2 \cdot 2 \equiv 4 \pmod{5}$，原式的结果就是 $2$。

为了更好的定义和计算模运算的除法，下面我们介绍模逆元。

2. 模逆元

模逆元定义：如果存在整数 $w$ 使得 $wy \equiv 1 \pmod{n}$，那我们称 $w$ 为 $y$ 在模 $n$ 下的逆元，写为 $y^{-1}$。

当且仅当 $y$ 和 $n$ 互质时（即 $\gcd(y,n)=1$），逆元存在。

有了逆元，我们就可以将模运算除法 $x/y$，转换为乘法 $xy^{-1}$ 进行计算了。

2.1 逆元的计算方法

那么，我们我们如何计算模 $n$ 下 $y$ 的逆元 $y^{-1}$ 呢？这一讲我们介绍两种常用方法：

2.1.1 穷举法

在模运算中， $Z_n$ 仅包含有限个元素，我们可以穷举其中的元素，找到 $w \in Z_n$ 使得 $wy \equiv 1 \pmod{n}$ 成立，则 $w$ 就是我们要找的 $y^{-1}$。举个例子，我们要找模 $5$ 下 $2$ 的逆元，那么我们可以计算 $Z_5$ 中所有元素和 $2$ 的乘积，然后计算除以 $5$ 的余数，找到余数为 $1$ 的那个值。如下所示，我们找到了 $2^{-1} \equiv 3 \pmod{5}$。

$Z_5$元素	和 2 相乘	余数
0	0	0
1	2	2
2	4	4
3	6	1
4	8	3

2.1.2 扩展欧几里得算法

之前的教程我们学习过，扩展欧几里得算法可以用来计算满足贝祖等式的系数，其实它也可以用来计算逆元，比穷举法更有效率。

当 y 的逆元 w 存在时，有 $\gcd(y, n)=1$，我们可以构建一个贝祖等式：

$$kn + wy = 1$$

将 $kn$ 移动到等式右侧，得到：

$$wy = 1 - kn$$

也就是

$$wy \equiv 1 \pmod{n}$$

因此，式子中的 $w$ 就是 $y$ 的逆元，我们可以利用扩展欧几里得算法求解它。

举个例子，我们可以用这个方法求解在模 $n = 69$ 下 $y = 7$ 的逆元，代码如下（你也可以尝试手算）。

def extended_euclidean_algorithm(a, b):
    x1, y1, x2, y2 = 1, 0, 0, 1

    while b:
        q = a // b
        a, b = b, a % b
        x1, x2 = x2, x1 - q * x2
        y1, y2 = y2, y1 - q * y2

    return a, x1, y1

# 示例
y = 7
n = 69
gcd_result, k, w = extended_euclidean_algorithm(n, y)
if gcd_result == 1:
    print(f'{n} 和 {y} 的最大公约数是 {gcd_result}, 逆元存在，为 {w}')
else:
    print(f'{n} 和 {y} 的最大公约数是 {gcd_result}, 逆元不存在')

# 69 和 7 的最大公约数是 1, 逆元存在，为 10

通过扩展欧几里得方法，我们得到 $y^{-1}=10$。可以验证 $yy^{-1}=70$，除以 $69$ 余 $1$，符合逆元的定义。

下面是递归版本的扩展欧几里得算法实现求模逆代码：

def get_inverse(a, N):
    if gcd(a, N) == 1:
        x, y = ext_gcd(a, N)
        return (x + N) % N
    print("No inverse!")
    return 0

下面，请你尝试解下面这道题：

$$6/9 \pmod{23} = ?$$

总结

这一讲，我们介绍了模运算中的除法和逆元的概念，并且介绍了两种求逆元的方法：穷举法和扩展欧几里得算法。模运算的除法与普通整数的除法差别很大，大家要通过练习来熟悉它。