专题进阶 · 数学算法推荐总顺序 · 第 93 / 148 课

理解同余的等价类,解释为什么模下除法需要逆元且不总存在。

先学会这些,再进入本课 欧几里得算法
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数学算法

模运算Modular Arithmetic

加减乘可在模下计算;除法需要逆元且逆元并不总存在。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

理解同余的等价类,解释为什么模下除法需要逆元且不总存在。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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+1GCD 为 1
反向代回1=3−2=3−(11−3×3)=4×3−11系数 4
验证3×4 mod 11=1逆元为 4

窄屏可左右滑动表格,阅读完整计算与理由。

可约分的前提是被除数的因子在当前模数下可逆。

04为什么这个方法成立

  1. 欧几里得过程保持余数为原输入的整数线性组合。
  2. 最后余数为 GCD;若为 1,a 的系数即逆元。
  3. 若 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

模 7 下 2 的逆元?

需要一点提示

找乘积余 1。

查看解析与答案

4,因为 2×4=8≡1。

练习 2 · 边界与辨析

模 8 下 3 可逆吗?

需要一点提示

先求 GCD。

查看解析与答案

可逆,gcd(3,8)=1,逆元 3。

练习 3 · 变式与迁移

组合数公式里分母模 p 为 0 怎么办?

需要一点提示

逆元不存在。

查看解析与答案

不能直接求逆;要分析质因子抵消、使用适合范围的递推或其他数论方法。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

CP-Algorithms · 欧几里得与最小公倍数CP-Algorithms · 二进制快速幂

理解之后,继续递进

继续当前专题:快速幂 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。