逆元模逆元的形式化定义设 a 为整数，m 为正整数。如果存在一个整数 x，使得
1ax ≡ 1 (mod m)
则称整数 x 是 a 模 m 的模逆元，记作 a ^ {-1} (mod m)
案例：求 3 ^ {-1} (mod 7)
我们需要寻找一个 x，满足 3 * x ≡ 1 (mod 7)
最后求出 x = 5
逆元存在性定理a 模 m 的逆元 a ^ {-1} (mod m) 存在的充要条件是 a 与 m 互素，即
1gcd(a,m) = 1
扩展欧几里得算法当模数 m 非常巨大时，我们不可能像前面那样用穷举法去试出逆元。我们需要高效的算法——扩展欧几里得算法
对任意正整数 a
2026-01-07288 字2 分钟
模运算规则
模运算规则为了后续案例的统一性，我们假定已知以下两个基本的同余关系作为基准：
12317 ≡ 2 (mod 5)11 ≡ 1 (mod 5)
加法规则定理：若 “a ≡ b (mod m)“ 且 “c ≡ d (mod m)“，则
1a + c ≡ b + d (mod m)
含义：两数之和的余数，等于它们各自余数之和的余数
带入案例
12317 + 11 ≡ 2 + 1 (mod 5)28 ≡ 3 (mod 5)
减法规则定理：若 “a ≡ b (mod m)“ 且 “c ≡ d (mod m)“，则
1a - c ≡ b - d (mod m)
含义：两数之差的余数，等于它们各自余
2026-01-06370 字2 分钟
同余
同余两个整数除以同一个数 n 的余数相同，我们就说它们在这个 n 的世界里是 “一路人”
例如：两个整数 a，b 除以 m 的余数相同，就说它们模 m 同余，记作
1a ≡ b (mod m)
整除性定义根据带余除法，我们可将 a 和 b 分别表示为
123a = q1 * m + r1 (0 ≤ r1 < m)b = q2 * m + r2 (0 ≤ r2 < m)
因为余数相同，所以 r1 = r2（参考上一节的带余除法）
此时，我们将两式相减
123a - b = (q1 * m + r1) - (q2 * m + r2) = (q1 - q2) *
2026-01-05131 字1 分钟
切比雪夫定理
切比雪夫定理对于任意整数 n > 1，在 n 和 2n 之间至少存在一个素数
n = 5，区间 (5, 10) 里有素数 7
n = 10，区间 (10, 20) 里有素数 11，13，17，19
n = 100，区间 (100, 200) 里随便就能找到 101
密钥生成时，我们需要一个 k 位的大素数（如 k = 2048）
随机选一个 k - 1 的奇数 a
切比雪夫定理直接告诉我们即使在最坏情况下，在 a 到 2a 区间内一定有素数
