模运算（包含模的逆运算）

模运算，就是取余数，在计算机语言中用%来表示。举个简单的例子，3 % 5 = 3。结果的取值范围在 0 与模之间，例如 res = X mod Y, 那么 res 的取值范围应该是[0,Y-1]。结果也可以用负数来看表示，3 % 5 = -2。 一般用正数的表现形式，如果出现负数，我们也该知道是怎么来的。

运算规律

模运算中同样有一些数学公式大家需要记住，基本跟四则运算比较相似。乘法大家需要注意下。

(A + B) % M = (A % M + B % M) % M

(A - B) % M = (A % M - B % M) % M

(A * B) % M = [(A % M) * (B % M)] % M

(A^n) % M = [(A % M)^n] % M

同样，模运算也满足结合律，分配律，交换律:

((A + B) % M + C) % M == (A + (B + C)%M) %M

((A * B) % M * C) % M == (A * (B * C)%M) %M

(A + B) % M == (B + A) % M

(A * B) % M == (B * A) % M

(A + B) % M == (A % M + B % M) % M

[(A + B) % M * C] % M == [(A * C) % M + (B * C) % M] % M

模的逆元

在数学中，如果两个数a和b满足 a * b ≡ 1 (mod m)，则我们称b是a在模m下的逆元。

通常表示为b = a^(-1) (mod m)。在模运算中，逆元一定存在于模数的范围内，因此逆元必须是正整数。如果逆元为负数，则与模运算的定义不符。因此，模的逆元一定是非负整数。

计算逆元最简单直观的方式就是辗转相除法，下面我将结合实例来讲解。

8^(-1) mod 29:

注意，此步骤替换的数均为每次计算的余数。如果最后出现的是负数，我们需要把它变成正数范围。

高阶次项取模：

比如 4^8 mod 59, 我们需要把次数一步步化小。

这就是我目前所掌握到的模的运算，如有问题，感谢您的指正！