title: 06. 模运算除法
tags:
  - zk
  - basic
  - modular arithmetic
  - modular inverse
  - modular division​

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}。

2.1.2 扩展欧几里得算法

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

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

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

也就是

因此，式子中的 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
​

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

总结

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