关于除法直接取模
在计算 \(\dfrac{a}{b} \bmod m\) 时，常规方法是利用乘法逆元。
但在一些特殊情况下，我们可以直接计算
\[\dfrac{a \bmod m}{b \bmod m} \bmod m
\]
证明：当 \(\gcd(a, m) = \gcd(b, m) = 1\) 时，有：
\[\dfrac{a}{b} \equiv \dfrac{a \bmod m}{b \bmod m} \pmod m
\]
使用逆元化成等价形式：
\[ab^{-1} \equiv (a \bmod m)(b \bmod m)^{-1} \pmod m
\]
其中 \(b^{-1}\) 是 \(b\) 在模 \(m\) 意义下的乘法逆元， \((b \bmod m)^{-1}\) 同理。
\[(a \bmod m)b^{-1} \equiv (a \bmod m \bmod m)(b \bmod m)^{-1} \pmod m
\]
因为 \(a \bmod m = a \bmod m \bmod m\)，所以：
\[(a \bmod m)b^{-1} \equiv (a \bmod m)(b \bmod m)^{-1}
\implies
ab^{-1} \equiv a(b \bmod m)^{-1}
\]
因为 \(\gcd(a,m)=1\)，所以上式可以化为：
\[b^{-1} \equiv (b \bmod m)^{-1} \pmod m
\]
该式与最开始要证明的式子等价，所以我们只要证明它即可。
下面我们使用推导扩展欧几里得算法的方法来证明。
设 \(x_1=b^{-1}, x_2=(b \bmod m)^{-1}\)，根据逆元的定义，有：
\[bx_1 \equiv 1 \pmod m
\]
\[(b \bmod m)x_2 \equiv 1 \pmod m
\]
因为 \(\gcd(b, m)=1\)，根据
\[\gcd(a,b) = \gcd(b, a \bmod b)
\]
可得
\[\gcd(b, m) = \gcd(b \bmod m, m) = 1
\]
由裴蜀定理得：
\[bx_1 + my_1 = 1
\]
\[(b \bmod m)x_2 + my_2 = 1
\]
联立两式：
\[bx_1 + my_1 = (b \bmod m)x_2 + my_2
\]
注意到 \(a \bmod b = a - (b \times \lfloor \frac{a}{b} \rfloor)\)，所以式子可变化为：
\[bx_1 + my_1 = bx_2 + m(y_2 - x_2 \times \lfloor \frac{b}{m} \rfloor)
\]
观察得出
\[x_1 = x_2
\]
故有：
\[b^{-1} \equiv (b \bmod m)^{-1} \pmod m
\]
得证。
受限于个人能力，也许过程繁琐甚至存在错误，欢迎大家指正。