模运算(MOD)

# 模运算(MOD)模运算（mod）是一种数学运算，它计算的是两个数相除后的余数，常用于许多数学和计算机科学问题中，尤其是在密码学、数论和计算机算法中。模运算具有非常重要的性质，理解这些性质对于很多高级应用至关重要。

# 1. 模运算的基本概念模运算可以用符号 "mod" 来表示。对于两个整数 aaa 和 bbb，以及一个正整数 nnn，模运算计算的是：

amod n=r a \mod n = r amodn=r

其中，rrr 是 aaa 除以 nnn 得到的余数，满足以下条件：

a=n×q+r a = n \times q + r a=n×q+r

其中：

qqq 是商（即整数部分）。rrr 是余数，满足 0≤r

# 2.1 加法性质对于任意的整数 aaa、bbb 和模数 nnn，有以下性质：

(a+b)mod n=[(amod n)+(bmod n)]mod n (a + b) \mod n = [(a \mod n) + (b \mod n)] \mod n (a+b)modn=[(amodn)+(bmodn)]modn

解释：将两个数分别取模后再相加，然后对模数进行取模，得到的结果和先加后取模是相同的。

示例：

(17+24)mod 5=(41)mod 5=1 (17 + 24) \mod 5 = (41) \mod 5 = 1 (17+24)mod5=(41)mod5=1

(17mod 5+24mod 5)mod 5=(2+4)mod 5=6mod 5=1 (17 \mod 5 + 24 \mod 5) \mod 5 = (2 + 4) \mod 5 = 6 \mod 5 = 1 (17mod5+24mod5)mod5=(2+4)mod5=6mod5=1

# 2.2 乘法性质对于任意的整数 aaa、bbb 和模数 nnn，有以下性质：

(a×b)mod n=[(amod n)×(bmod n)]mod n (a \times b) \mod n = [(a \mod n) \times (b \mod n)] \mod n (a×b)modn=[(amodn)×(bmodn)]modn

解释：将两个数分别取模后再相乘，然后对模数进行取模，得到的结果和先乘后取模是相同的。

示例：

(17×24)mod 5=408mod 5=3 (17 \times 24) \mod 5 = 408 \mod 5 = 3 (17×24)mod5=408mod5=3

(17mod 5×24mod 5)mod 5=(2×4)mod 5=8mod 5=3 (17 \mod 5 \times 24 \mod 5) \mod 5 = (2 \times 4) \mod 5 = 8 \mod 5 = 3 (17mod5×24mod5)mod5=(2×4)mod5=8mod5=3

# 2.3 减法性质对于任意的整数 aaa、bbb 和模数 nnn，有以下性质：

(a−b)mod n=[(amod n)−(bmod n)]mod n (a - b) \mod n = [(a \mod n) - (b \mod n)] \mod n (a−b)modn=[(amodn)−(bmodn)]modn

解释：将两个数分别取模后再相减，然后对模数进行取模，得到的结果和先减后取模是相同的。

示例：

(17−24)mod 5=(−7)mod 5=3 (17 - 24) \mod 5 = (-7) \mod 5 = 3 (17−24)mod5=(−7)mod5=3

(17mod 5−24mod 5)mod 5=(2−4)mod 5=−2mod 5=3 (17 \mod 5 - 24 \mod 5) \mod 5 = (2 - 4) \mod 5 = -2 \mod 5 = 3 (17mod5−24mod5)mod5=(2−4)mod5=−2mod5=3

# 2.4 幂运算性质对于任意的整数 aaa、bbb 和模数 nnn，有以下性质：

abmod n=(amod n)bmod n a^b \mod n = (a \mod n)^b \mod n abmodn=(amodn)bmodn

解释：计算一个数的幂时，可以先对底数取模再进行幂运算，最后取模，结果与先计算幂再取模是相同的。

示例：

173mod 5=4913mod 5=3 17^3 \mod 5 = 4913 \mod 5 = 3 173mod5=4913mod5=3

(17mod 5)3mod 5=23mod 5=8mod 5=3 (17 \mod 5)^3 \mod 5 = 2^3 \mod 5 = 8 \mod 5 = 3 (17mod5)3mod5=23mod5=8mod5=3

# 3. 负数和模运算对于负数的模运算，很多人会有些困惑。实际上，模运算的结果总是非负的，并且小于模数。为了确保结果正确，可以使用以下公式将负数转换为正数的模：

amod n=((amod n)+n)mod n a \mod n = ((a \mod n) + n) \mod n amodn=((amodn)+n)modn

示例：

(−17)mod 5 (-17) \mod 5 (−17)mod5

计算 −17mod 5-17 \mod 5−17mod5 时，我们首先计算 −17÷5=−4.4-17 \div 5 = -4.4−17÷5=−4.4，商为 -5，余数是 −17−(−5×5)=−17+25=8-17 - (-5 \times 5) = -17 + 25 = 8−17−(−5×5)=−17+25=8。 所以：

−17mod 5=8mod 5=3 -17 \mod 5 = 8 \mod 5 = 3 −17mod5=8mod5=3

# 4. 模运算中的快速幂算法对于非常大的指数，直接计算 abmod na^b \mod nabmodn 会非常耗时。为此，常用的算法是 快速幂算法，也称为 二分法幂算法。它通过递归地将幂分解为小幂，从而显著提高计算效率。

快速幂算法的基本思想：

对于 abmod na^b \mod nabmodn，如果 bbb 是偶数，则：

abmod n=(ab/2mod n)2mod n a^b \mod n = (a^{b/2} \mod n)^2 \mod n abmodn=(ab/2modn)2modn

如果 bbb 是奇数，则：

abmod n=a×(ab−1mod n)mod n a^b \mod n = a \times (a^{b-1} \mod n) \mod n abmodn=a×(ab−1modn)modn

这种方法能将计算复杂度从 O(b)O(b)O(b) 降低到 O(log⁡b)O(\log b)O(logb)，显著提高效率。