数学重学 - 09 模运算与整除

数学重学
,

这是 数学重学路线图 阶段二的子页面

📌 已有相关笔记：取余与模运算、密码学数学，本页从数学角度系统梳理并补充后端/大数据实战

为什么要学模运算

模运算是计算机科学中 出现频率最高 的数学运算之一

哈希表、分库分表、负载均衡、密码学——全都离不开它

你每天写的代码里一定用到了取模，只是你可能没意识到

安全方向：RSA 加密的核心就是模幂运算

大数据方向：一致性哈希解决扩缩容问题

后端方向：分库分表路由、轮询负载均衡

核心概念（直觉先行）

取模的直觉：钟表

现在是 13 点，钟表上显示几点？→ 1 点

13 mod 12 = 1

钟表就是一个 模 12 的系统：数到 12 就归零重来

再举例：25 mod 12 = 1（25 点 = 次日凌晨 1 点）

取模就是”绕了一圈又一圈之后，剩下多少”

数学定义

a mod n = r，其中 a = n × q + r（0 ≤ r < n）

q 是商（被丢弃的”整圈数”），r 是余数（我们要的）

例：17 mod 5 = 2，因为 17 = 5 × 3 + 2

整除

如果 a mod n = 0，就说 n 整除 a，记作 n | a

例：12 mod 3 = 0，所以 3 | 12（3 整除 12）

整除判断规则

快速判断一个数能否被某些数整除，面试/日常都有用

能被 2 整除

末位是偶数（0、2、4、6、8）

能被 3 整除

各位数字之和能被 3 整除

例：123 → 1+2+3=6，6 能被 3 整除 ✓

能被 4 整除

末两位组成的数能被 4 整除

例：1324 → 24 ÷ 4 = 6 ✓

能被 5 整除

末位是 0 或 5

能被 8 整除

末三位组成的数能被 8 整除

能被 9 整除

各位数字之和能被 9 整除

例：729 → 7+2+9=18，18 能被 9 整除 ✓

能被 11 整除

奇数位与偶数位数字之和的差能被 11 整除

例：1001 → (1+0) - (0+1) = 0，0 能被 11 整除 ✓

模运算的数学性质

加法取模

(a + b) mod n = ((a mod n) + (b mod n)) mod n

例：(17 + 23) mod 5 = (2 + 3) mod 5 = 5 mod 5 = 0

人话：先各自取模再加，和先加再取模，结果一样

乘法取模

(a × b) mod n = ((a mod n) × (b mod n)) mod n

例：(17 × 23) mod 5 = (2 × 3) mod 5 = 6 mod 5 = 1

人话：大数相乘怕溢出？先各自取模缩小，再乘再取模

这个性质是 RSA 加密 能高效计算的关键！

减法取模

(a - b) mod n = ((a mod n) - (b mod n) + n) mod n

加 n 是为了避免负数

除法 ⚠️ 不直接成立

(a / b) mod n ≠ (a mod n) / (b mod n) mod n

除法需要用 模逆元：b 的模逆元 b⁻¹ 满足 b × b⁻¹ ≡ 1 (mod n)

这在 RSA 中很关键 → 详见 密码学数学

模幂运算（快速幂）

计算 a^b mod n，不需要先算出 a^b 再取模（那会天文数字大）

利用 (a×b) mod n 的性质，边乘边取模

Python 内置：pow(a, b, n) 就是高效的模幂运算

公式与推导（附人话翻译）

同余

a ≡ b (mod n) 表示 a 和 b 除以 n 的余数相同

等价于：n | (a - b)，即 n 整除 (a-b)

例：17 ≡ 2 (mod 5)，因为 17 - 2 = 15，5 | 15

人话：在钟表上，17 点和 5 点（mod 12）都指向同一个位置吗？不是，17 mod 12 = 5，5 mod 12 = 5。所以 17 ≡ 5 (mod 12) ✓

费马小定理

若 p 是素数且 a 不是 p 的倍数，则 a^(p-1) ≡ 1 (mod p)

用途：RSA 的数学基础之一

欧拉定理（费马小定理的推广）

a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数

用途：RSA 加密的核心定理 → 详见 密码学数学

Python 代码实战

基本取模操作

1
2
3
4
5
6
7
8
9
10
11
12
# Python 的取模运算
print(17 % 5)     # 2
print(-17 % 5)    # 3  ← Python 的负数取模结果总是非负！
# 注意：C/Java 中 -17 % 5 = -2，和 Python 不同

# divmod 同时得到商和余数
q, r = divmod(17, 5)
print(f"17 ÷ 5 = {q} 余 {r}")  # 17 ÷ 5 = 3 余 2

# 模幂运算（高效版，不会溢出）
result = pow(2, 100, 1000000007)
print(f"2^100 mod 10^9+7 = {result}")

分库分表路由模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class ShardRouter:
"""分库分表路由器——模运算的经典应用"""

def __init__(self, db_count=4, table_count=16):
    self.db_count = db_count
    self.table_count = table_count

def route(self, user_id):
    """根据 user_id 决定数据存在哪个库的哪张表"""
    db_index = user_id % self.db_count
    table_index = user_id % self.table_count
    return {
        'user_id': user_id,
        'database': f'db_{db_index}',
        'table': f'user_{table_index:02d}'
    }

def batch_route(self, user_ids):
    """批量路由，看看数据分布是否均匀"""
    distribution = {}
    for uid in user_ids:
        info = self.route(uid)
        key = f"{info['database']}.{info['table']}"
        distribution[key] = distribution.get(key, 0) + 1
    return distribution

router = ShardRouter(db_count=4, table_count=16)

# 单个路由
print(router.route(12345))
# {'user_id': 12345, 'database': 'db_1', 'table': 'user_09'}

# 批量路由看分布
import random
user_ids = [random.randint(1, 1_000_000) for _ in range(10000)]
dist = router.batch_route(user_ids)

# 按库统计
db_counts = {}
for key, count in dist.items():
db = key.split('.')[0]
db_counts[db] = db_counts.get(db, 0) + count

for db, count in sorted(db_counts.items()):
print(f"{db}: {count} 条 ({count/100:.1f}%)")

一致性哈希环（简单实现）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import hashlib
from bisect import bisect_right

class ConsistentHash:
"""
一致性哈希：解决普通取模在扩缩容时大量数据迁移的问题

普通取模问题：
  hash(key) % 3 → 加一台变 hash(key) % 4 → 几乎所有数据都要迁移

一致性哈希：
  把 0~2^32 想象成一个环，服务器和数据都映射到环上
  数据顺时针找到最近的服务器 → 增减节点只影响相邻数据
"""
def __init__(self, replicas=150):
    self.replicas = replicas  # 虚拟节点数，让分布更均匀
    self.ring = []            # 有序的哈希值列表
    self.node_map = {}        # 哈希值 → 真实节点

def _hash(self, key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % (2**32)

def add_node(self, node):
    for i in range(self.replicas):
        virtual_key = f"{node}#virtual{i}"
        h = self._hash(virtual_key)
        self.ring.append(h)
        self.node_map[h] = node
    self.ring.sort()

def remove_node(self, node):
    self.ring = [h for h in self.ring if self.node_map.get(h) != node]
    self.node_map = {h: n for h, n in self.node_map.items() if n != node}

def get_node(self, key):
    if not self.ring:
        return None
    h = self._hash(key)
    idx = bisect_right(self.ring, h) % len(self.ring)
    return self.node_map[self.ring[idx]]

# 测试
ch = ConsistentHash(replicas=150)
for server in ['server-A', 'server-B', 'server-C']:
ch.add_node(server)

# 看 1000 个 key 的分布
counts = {}
for i in range(1000):
node = ch.get_node(f"user:{i}")
counts[node] = counts.get(node, 0) + 1

print("=== 3 台服务器的分布 ===")
for node, count in sorted(counts.items()):
print(f"{node}: {count} ({count/10:.1f}%)")

# 加一台服务器，看迁移量
old_mapping = {f"user:{i}": ch.get_node(f"user:{i}") for i in range(1000)}
ch.add_node('server-D')
new_mapping = {f"user:{i}": ch.get_node(f"user:{i}") for i in range(1000)}

migrated = sum(1 for k in old_mapping if old_mapping[k] != new_mapping[k])
print(f"\n加入 server-D 后，需要迁移的 key: {migrated}/1000 ({migrated/10:.1f}%)")
print("如果用普通取模，迁移量约 75%，一致性哈希大大减少了迁移！")

整除性判断工具

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def divisibility_check(n):
"""一次性检查所有常见整除规则"""
results = {}
results[2] = n % 2 == 0
results[3] = sum(int(d) for d in str(abs(n))) % 3 == 0
results[4] = n % 4 == 0
results[5] = n % 5 == 0
results[8] = n % 8 == 0
results[9] = sum(int(d) for d in str(abs(n))) % 9 == 0

# 11 的判断：奇偶位差
digits = [int(d) for d in str(abs(n))]
odd_sum = sum(digits[i] for i in range(0, len(digits), 2))
even_sum = sum(digits[i] for i in range(1, len(digits), 2))
results[11] = (odd_sum - even_sum) % 11 == 0

print(f"=== {n} 的整除性检查 ===")
for divisor, is_divisible in sorted(results.items()):
    status = "✓ 能整除" if is_divisible else "✗ 不能"
    print(f"  被 {divisor:2d} 整除: {status}")

return results

divisibility_check(123456)
divisibility_check(1001)

负载均衡轮询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class RoundRobinBalancer:
"""轮询负载均衡——最简单的取模应用"""
def __init__(self, servers):
    self.servers = servers
    self.counter = 0

def next_server(self):
    server = self.servers[self.counter % len(self.servers)]
    self.counter += 1
    return server

balancer = RoundRobinBalancer(['web-01', 'web-02', 'web-03'])
for i in range(9):
print(f"请求 {i+1} → {balancer.next_server()}")
# 输出：web-01, web-02, web-03, web-01, web-02, web-03, ...

实际应用场景

后端方向

哈希表取模选桶：hash(key) % bucket_count 决定放哪个桶

分库分表：user_id % 16 决定分到哪个库（见上面代码）

负载均衡轮询：request_count % server_count

分页计算：第 N 页的 offset = (N-1) × page_size

周期性任务：tick % interval == 0 时触发

大数据方向

一致性哈希：解决扩缩容时数据迁移问题（见上面代码）

MapReduce 分区：hash(key) % reduce_count 决定分到哪个 reducer

数据采样：id % 100 < 5 抽取 5% 样本

时间窗口聚合：timestamp % window_size 决定落入哪个窗口

安全方向

RSA 加密：核心是模幂运算 m^e mod n → 详见 密码学数学

哈希碰撞：两个不同输入 hash 相同 = hash 值模空间太小

验证码有效期：current_time % ttl 判断是否过期

Token 轮换：基于时间的一次性密码 TOTP = HMAC(key, time // 30)

常见误区

❌ 误区1：Python 的 % 和 C/Java 的 % 一样

✅ Python 对负数取模结果总是非负：-7 % 3 = 2（不是 -1）

✅ C/Java 中 -7 % 3 = -1，这在跨语言移植时是坑

❌ 误区2：分库分表用 user_id % N 就完事了

✅ N 改变时所有数据都要迁移！所以需要一致性哈希或翻倍扩容

❌ 误区3：取模运算很慢

✅ 现代 CPU 的整数取模是硬件指令，非常快

✅ 如果模数是 2 的幂，编译器会优化成位运算 & (n-1)

❌ 误区4：哈希取模选桶数随便选

✅ 桶数选素数时分布更均匀（减少冲突）

✅ HashMap 选 2 的幂是为了用位运算加速，但需要好的哈希函数补偿

练习题

题1：钟表问题

现在是周三（用 3 表示），100 天后是星期几？

提示：(3 + 100) % 7

答案：

(3 + 100) % 7 = 103 % 7 = 5 → 周五

题2：分库分表

有 8 个数据库（db_0 到 db_7），用 user_id % 8 分库

user_id = 1000, 1001, 1007, 1008 分别在哪个库？

答案：

1000 % 8 = 0 → db_0

1001 % 8 = 1 → db_1

1007 % 8 = 7 → db_7

1008 % 8 = 0 → db_0

题3：模运算性质

不用计算器，求 (123456789 × 987654321) % 10 的值

提示：只看末位就行

答案：

123456789 mod 10 = 9

987654321 mod 10 = 1

9 × 1 = 9

答案是 9

题4：负数取模

Python 中 -13 % 5 等于多少？C 语言中呢？

答案：

Python：-13 % 5 = 2（-13 = 5×(-3) + 2）

C：-13 % 5 = -3（C 的余数符号跟被除数一致）

题5：一致性哈希

如果有 3 台服务器用普通取模，加 1 台变成 4 台，理论上有多少比例的 key 需要迁移？

如果用一致性哈希（理想情况），比例是多少？

答案：

普通取模：约 75%（只有 hash % 3 == hash % 4 的 key 不用迁，概率约 25%）

一致性哈希：理想情况约 25%（1/4，只有分配到新节点的需要迁移）

上一章 目录 下一章
08-进制与位运算 数学重学路线图 10-布尔代数与逻辑