01先把问题说具体
在模 11 的世界里,3x≡1 的解是什么?为什么不能把普通除法 1/3 直接取模?
02一步步得到方法
模运算保留的是余数关系
a≡b (mod m) 表示 m 整除 a−b。加、减、乘会保持同余,因此大表达式可在每一步取模,控制中间规模。例如 (8+7) mod 11=4,先各自取模再加结果相同。
除法不同:模 m 下除以 a 实际是乘某个 x,使 ax≡1。这个 x 称为逆元。逆元存在当且仅当 gcd(a,m)=1;否则乘 a 会把不同余数映射到同一类,无法唯一反转。
扩展欧几里得给出逆元
若 ax+my=1,两边模 m 就有 ax≡1,因此 x 的余数是逆元。扩展欧几里得沿取余递推求出这组系数;本代码用迭代形式追踪 a 的系数。
例如 3×4−11×1=1,所以 3 在模 11 下逆元为 4。模 6 下 2 没有逆元,因为 2x 永远是偶余数,不可能等于 1。
同余允许加减乘,不自动允许除
a≡b(mod m) 表示差值能被 m 整除。加法和乘法可以在中间步骤不断取模,因为同余关系对这些运算封闭;这正是大数计算可以压缩到余数范围的原因。
除法相当于乘逆元,而 b 的模逆元仅在 gcd(b,m)=1 时存在。比如模6中,2没有逆元,因为2的倍数永远不可能同余于1,不能照搬普通实数除法。
03把一个小例子完全算清楚
a=3,m=11。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 取余关系 | 11=3×3+2,3=1×2+1 | GCD 为 1 |
| 反向代回 | 1=3−2=3−(11−3×3)=4×3−11 | 系数 4 |
| 验证 | 3×4 mod 11=1 | 逆元为 4 |
窄屏可左右滑动表格,阅读完整计算与理由。
可约分的前提是被除数的因子在当前模数下可逆。
04为什么这个方法成立
- 欧几里得过程保持余数为原输入的整数线性组合。
- 最后余数为 GCD;若为 1,a 的系数即逆元。
- 若 GCD>1,则它整除 ax 与 m,不可能整除 1,故逆元不存在。
05把推导翻译成代码
Python · 可独立运行的教学实现
def inverse(a,mod):
assert mod > 1
old_r,r = a%mod,mod
old_s,s = 1,0
while r:
q = old_r//r
old_r,r = r,old_r-q*r
old_s,s = s,old_s-q*s
return old_s%mod if old_r == 1 else None逐个理解关键决定
old_s,s = s,old_s-q*s- 与余数做相同线性变换,追踪原 a 的系数。
old_r == 1- 不能省略存在性检查;GCD 不为 1 时没有逆元。
06时间、空间与实现范围
扩展欧几里得取余轮数 O(log mod),只保存常数个大整数。
费马小定理形式 a^(p−2) 只在 p 为质数且 a 不被 p 整除时适用,不能对任意模数照用。
07改变条件,检查哪里会出错
模下把两边都除以非零数
非零不代表可逆,例如模 6 的 2。
把负余数的语言差异忽略
不同语言的 % 对负数约定可能不同,需要统一到期望的0到m−1范围。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
模 7 下 2 的逆元?
需要一点提示
找乘积余 1。
查看解析与答案
4,因为 2×4=8≡1。
模 8 下 3 可逆吗?
需要一点提示
先求 GCD。
查看解析与答案
可逆,gcd(3,8)=1,逆元 3。
组合数公式里分母模 p 为 0 怎么办?
需要一点提示
逆元不存在。
查看解析与答案
不能直接求逆;要分析质因子抵消、使用适合范围的递推或其他数论方法。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂