06.模运算除法

title: 06. 模运算除法 tags: zk basic modular arithmetic modular inverse modular division WTF zk 教程第 6 讲：模运算除法 模运算的除法和普通整数的除法有很大区别，理解它非常重要。这一讲，我们将介绍模运算除法，模逆，和计算逆元的方法。 除法 上一讲我们介绍了模运算中的加法和乘法，和普通加法/乘法类似。但模运算的除法和普通除法很不同。如果我们将整数除法运用到模运算中，会产生奇怪的结果。举个例子，我们知道 $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$，...