模运算与计算中的代数

时钟加小时会绕固定循环，模运算把同一思想用于所有整数，包括负数。加乘仍良定义，除法却不同：非零剩余类可能无逆元。实数上合法的约去步骤可把真同余变成假结论。

本课连接整数整除与合法模运算，推导欧几里得不变式，计算贝祖证书，识别可逆类，跟踪快速幂，区分群、环、域。最后区分二进制域算术与机器字算术，并明确小校验和实际能建立什么。

回忆检查：操作整数等式、展开有限积、解释不变式与递减整数变式。按需复习模块 01、模块 04。核心不要求图或计数模块。除另声明外，模数都是整数 m≥2。

整数 a,b 的 a 整除 b，写 a|b，表示存在整数 k 使 b=ak。这是整数域存在命题，不表示 a/b 为整数，也不要求 b 大于 a。例如 3|−12，因为 −12=3·(−4)。每整数整除零，零只整除零。后面的素数与 gcd 定义避免把特殊零情况与正因数混淆。

若 a|b 且 a|c，则 a 整除任意整数线性组合 xb+yc：代 b=as,c=at 得 a(xs+yt)。若 a|b,b|c，乘见证得 a|c。它们说明减去另一整数的整数倍为何保共同因数。系数必须整数，任意实数组合不保持整除。

带余除法定理：任意整数 a 与正整数 m，唯一整数 q,r 满足 a=qm+r，0≤r<m。名称中的“算法”指商余性质，不要求特定实现。存在证明取 q=floor(a/m)，r=a−qm，取整不等式给余数范围，包括负 a。

唯一性：若 qm+r=q′m+r′ 且两余数合范围，则 (q−q′)m=r′−r。右边绝对值小于 m，区间内唯一 m 倍数为零，因此 q=q′,r=r′。截断除法允许负余数等其他约定会改变表示规则；本数学代表与 Python 正整数模数的余数一致。

素数为大于一的整数 p，正因数只有一与 p。大于一且非素数叫合数。一既非素也非合，负素数不在约定内。把大于一的正整数递归拆合因子成更小因子，直到全素；对整数作强归纳证明素因子分解存在。

算术基本定理还声明除顺序外唯一。关键引理：素数整除乘积就至少整除一个因子。下一节用贝祖说明。反复用引理把一分解的素数与另一分解相同素数匹配，约去该正整数因子并继续。存在与唯一是不同义务，列一种成功分解只证明该输入存在。

素分解是数学描述，不声称寻找任意巨大整数因子都快。小例用精确算术与初等论证。欧几里得不需要先分解两输入就能求 gcd，是不变式算法的优势。整数大小增长时要计位操作，不能把巨大积与除法当恒成本。

非负 a,b 不全零时，最大公因数 gcd(a,b) 是同时整除两者的最大正整数。共同正因数非空，且被非零输入界，故存在。a>0 时 gcd(a,0)=a。任意符号用 gcd(|a|,|b|)。全零无最大正公因数，软件常另约 gcd(0,0)=0。

若 a=qb+r，则 (a,b) 与 (b,r) 共同因数集合相同。a,b 的因数也除 r=a−qb；b,r 的因数也除 a=qb+r。故 gcd相等。欧几里得算法在 b 非零时反复把 (a,b) 换 (b,a modb)，不变式是原 gcd 不变，而不只是余数递减。

终止由非负第二分量严格递减：非零 b 下 0≤r<b。非负整数不可能无限严格下降。b=0 时第一分量根据 gcd(a,0) 与不变式就是原 gcd。保持说明若停则正确，递减变式另证明一定停，与模块 04 一样两者都要。

贝祖恒等式说存在整数 x,y 使 ax+by=gcd(a,b)。扩展欧几里得跟踪两组系数，初始 a=1·a+0·b，b=0·a+1·b。第一行减 q 倍第二行时，余数与系数同步更新，再交换两行保表示不变式。最终非零余数因此携带具体证书。

系数通常不唯一。若 ax+by=d，对任意整数 t，把 x 改 x+(b/d)t、y 改 y−(a/d)t 保等式。实验返回其他系数仍可正确，要查实际等式与 gcd，而非硬要求特定对。零输入也有恒等式，全零软件约定返回零表示，并非最大正因数。

若 p 素且 p 不整除 a，则 gcd(p,a)=1，贝祖给 px+ay=1。若 p|ab，乘 b 得 pxb+aby=b，左两项都被 p 整除，故 p|b。这证 p|ab 蕴涵 p|a 或 p|b，支撑分解唯一性，没有假设任意合因数也有此性质。

例如 6|2·3，却不除 2 或 3，把“素数”改“任意整数”会假。精确假设在模约去再次重要，非零因子与和模数互素的因子不同。贝祖把互素变为逆元，允许合法约去。

欧几里得除法次数对较小正输入为对数。一种证明：第二分量每两次至少减半。首余 r≤b/2 已满足；若 r>b/2，下次 b 除 r 的余 b−r<b/2。此论证界余数步数，不证明每次长整数除法都恒时间。

整数 a,b、固定 m≥2，模 m 同余 $a\equiv b\pmod m$ 表示 m|(a−b)，不是整数相等。同余因 m|0 自反，见证取负对称，可整除差相加传递。等价类包含相差 m 整数倍的所有整数。

a 的类写 [a]ₘ，含所有整数 k 的 a+km。带余定理给每类唯一零到 m−1 代表 a modm。因此 [−17]₇=[4]₇，但 −17 与四仍不同整数。类相等可以，不能替换成原整数相等。

定义类加乘 [a]+[b]=[a+b]，[a][b]=[ab]。良定义要求不依赖代表。若 a′=a+km,b′=b+ℓm，和差为 (k+ℓ)m，积差为 m(kb+ℓa+kℓm)，都可被 m 整除。故可先缩减操作数再算而不改最终剩余类。

减法是加加法逆元：[a] 的加法逆为 [−a]。例如 −3 mod7=4，因为 3+4≡0，加法逆总存在。别与满足 ab≡1 而非 a+b≡0 的乘法逆元混淆，“逆”依选定运算，歧义时说明运算。

非负模幂是重复类乘，指数零取空积 [1]。这个代数约定使零基零指数算法也返一，并不解决所有分析中的 0⁰，仍需域声明。负指数要求乘法逆，不能为任意剩余类定义。

剩余类时钟中，加 a 是固定步数旋转，总为位置排列，因为减 a 可逆转。乘 a 则可能合并不同位置。模六一与四乘二都得二，下一节给乘法映射何时为排列的准确条件。

比较规范代表大小只是显示约定。a≡b 不意味着普通大小或符号一致，同样取模不保不等式：6<8，但 6 mod7=6 大于 8 mod7=1。同余支持经过证明的代数运算，不是所有整数操作。

{0,…,m−1} 常代指类本身，跨软件时应记解释。Python 的整数三在类型中不携带模数，程序必须一致应用模数。不同模数剩余类若无声明映射，不能仅因代表数字相同就混作一次模计算。

a 的模 m 乘法逆元为满足 ab≡1 的类，存在当且仅当 gcd(a,m)=1。必要：ab−1=km 即 ab−km=1，所有共同因数除一。充分：gcd 一时贝祖给 ax+my=1，x 即逆。这是双向定理，不是样例支持的经验。

逆若存在则类唯一。ab≡1,ac≡1 时乘 b 得 b≡c，等价于用已建立逆约去 a。扩展欧几里得可给三模七的逆 −2，规范代表 −2 mod7=5。唯一说类，不说该类所有整数代表只一个。

从 ax≡ay modm 约到 x≡y，在 gcd(a,m)=1 时可乘逆合法。无条件会失败：模六 2·1≡2·4，一与四却不同余。把普通整数代表除二不保原模数，这里剩的是 x≡y mod3，是更弱不同结论。

一般 d=gcd(a,m)，m|a(x−y) 的整数整除式除 d 后，a/d 与 m/d 互素，贝祖约去给 (m/d)|(x−y)。因此约去后的模数应为 m/d。精确整数等式的除法与类求逆不同，写中间整除式可防除号隐藏区别。

线性同余 ax≡b modm 可解当且仅当 d=gcd(a,m) 整除 b。必要因 d 除 ax 与 m，故除 b。充分把 a,b,m 除 d，a/d 在模 m/d 可逆，得一个约简解 x₀。原模数代表解为 x₀+k(m/d)，k=0,…,d−1；模 m 各不同，任意解与 x₀ 差 m/d 倍，故穷尽。

4x≡2 mod6 的 d=2，约简 2x≡1 mod3，二的逆是二，故 x≡2 mod3，原代表二与五。2x≡1 mod6 的 d 不除一，无解。方程可以零、一或多解，把非零系数都当唯一除数会丢掉区别。

d=m 时，如 a≡0，按 m 是否除 b 决定：b≡0 时每类都解 0x≡0，否则无解。约简模数一是平凡同余，不属于其他处 m≥2 的非平凡代数结构。应另说明，不能称模一类为通常非平凡域。

非零类有另一个非零类使乘积零，称零因子。模六二乘三零。素模 p 每非零都互素、可逆，无此对；零积乘逆会强迫另一因子零。这说明素模与合模的代数差别。

重复平方计算 aᴱ modm，E 为非负整数，避免 E 次连乘。维护结果 r、当前基 b、余指数 e，初始 1,a modm,E。不变式 rbᵉ≡aᴱ。e 奇时 r 乘 b，再 b 平方，e 取 floor(e/2)。偶 e=2k 得 r(b²)ᵏ，奇 e=2k+1 得 (rb)(b²)ᵏ，都与旧积同类。

正余指数严格下降，终止 e=0，不变式给 r≡aᴱ。零指数无迭代返一，按空积约定。每乘后约简保类且把存储代表限到 m−1，避免巨大未约简幂；乘法自身位成本仍随模数大小。

E>0 迭代数 floor(log₂E)+1，即二进制长度，每次至多两模乘，包含 E=0 边界为 O(log(E+1)) 次。这对指数数值是对数，对指数位长是线性，不是编码长度对数。大模数使每操作更贵，乘次数不是完整运行证明。

费马小定理：p 素且 p 不除 a 时 aᵖ⁻¹≡1 modp。证明乘 a 排列非零剩余类，因为 a 可逆。乘所有 p−1 输出得 aᵖ⁻¹(p−1)!≡(p−1)!，各阶乘因子非零可逆，乘积可约，余结论。

a 被 p 整除时上述非零结论假；常用全整数形式 aᵖ≡a 需分别处理零与非零类。合模一般不服素定理：2⁵ mod6=2 非一，连互素基五的 5⁵ mod6 也为五。某些合数会通过特定幂检查，因此单次成功不自动证明素性。

p 素、a 非零时逆可算 aᵖ⁻²，由乘 a 与费马推出。条件仍必要；扩展欧几里得对任意互素模数都适用，不要求素性。实验用 gcd 条件与 Python 精确模幂约定，不滥用素数公式。

中国剩余定理（CRT）对互素正模 m,n 声明：给定模 m 与模 n 剩余类，唯一确定模 mn 类。若 u 为 n 模 m 的逆，v 为 m 模 n 的逆，x=anu+bmv 在两模给 a,b。每项在一模消失，在另一模供所需代表。

一般唯一性：m,n 均除差 Δ，写 Δ=mk，互素从 n|mk 约去 m 得 n|k，因此 mn|Δ。不互素时兼容条件改变，组合周期不一定 mn。例如 x≡0 mod2 与 x≡1 mod4 不可能，后一条件使数奇。互素构造不声称能处理这冲突。

代数结构指定集合、操作与律。群有封闭结合操作、单位元、每元素逆；操作交换叫阿贝尔群。整数加法为阿贝尔群，零单位，−a 为逆；整数乘法非群，零及多数整数无整数乘逆。

模 m 类在加法下为阿贝尔群。乘法下可逆元（units），即与 m 互素的类，形成群：一单位，可逆元积的逆由两逆相乘获得，逆仍可逆。合模全部非零类不一定成群，零因子可乘为零也缺逆。这里 unit 是可逆元素，不要与运算的 identity（单位元）混淆。

有单位元交换环有阿贝尔加法群，以及封闭、结合、交换、有单位元的乘法，对加法分配。本课非平凡环 1≠0，整数与模 m 类均例。良定义使加乘分配在取模后保持。环不承诺每非零可除，这是域多出的条件。

域是 1≠0 的交换环且每非零有乘逆。有理数、实数为域，整数非域，因二无整数逆。模 p 是域当且仅当 p 素：素 p 由 gcd 保逆；合 m=uv，1<u,v<m，非零 [u],[v] 积零，域不允许。

许多定宽无符号操作绕模 2ʷ，但表示与语言仍决定行为。模 256 环有零因子，16·16≡0，非域。Python 整数不自动定宽回绕，脚本需显式约简。这描述例子的模型，不声称覆盖每语言有符号溢出或每硬件指令。

校验和可取字节零到 255 的 c(values)=sum(values) mod7，输出七种类。同输入必同输出，所以不同校验和证明输入不同；同输出不证输入同。[1,2] 与 [0,3] 都三，反序 [2,1] 也三，把允许字节加七仍同剩余。

较大输入集压到小输出集必有碰撞，单射需每不同输入一个不同输出。这个和更有易构造碰撞且忽略顺序。它检测一些偶然变化，如在范围内单字节加一，却漏补偿变化、换位与七倍变化。报告要说明具体检测性质，不宣传普遍检测。

模算术也用于密码数学，但有素数、逆、快速幂本身不建立安全。小校验和或小模示例无抵抗攻击者结论。安全结论需指定构造、威胁模型、假设与远超此计算的分析。本课迁移目标是识别运算与证据限度，不设计生产安全系统。

Python 3.11+ 标准库即可。先预测恒等式与反例；下载脚本与下方捕获输出的执行源完全相同。

实验 A 欧几里得与扩展算法

预测：252,105 的 gcd 与贝祖系数。运行：看商行，查每等式。解释：零输入尤其 (0,0) 为何要另约定。修改：加 gcd 一的正数对，验证适当模数下系数给逆。负输入在该实验域外。

下载 lab1_euclid.py

"""Euclid and extended Euclid for nonnegative integer inputs."""
from math import gcd

def euclid_trace(a, b):
    if a < 0 or b < 0:
        raise ValueError("This lab uses nonnegative integers")
    rows = []
    while b:
        q, r = divmod(a, b)
        rows.append((a, b, q, r))
        a, b = b, r
    return a, rows

def extended_gcd(a, b):
    if a < 0 or b < 0:
        raise ValueError("This lab uses nonnegative integers")
    old_r, r = a, b
    old_x, x, old_y, y = 1, 0, 0, 1
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_x, x = x, old_x - q * x
        old_y, y = y, old_y - q * y
    return old_r, old_x, old_y

value, rows = euclid_trace(252, 105)
for a, b, q, r in rows:
    print(f"{a} = {q}*{b} + {r}")
print("Last nonzero remainder / gcd:", value)
for a, b in [(252, 105), (12, 18), (0, 7), (9, 0), (0, 0)]:
    d, x, y = extended_gcd(a, b)
    assert d == gcd(a, b) and a * x + b * y == d
    print(f"a={a}, b={b}: gcd={d}, x={x}, y={y}; a*x+b*y={a*x+b*y}")
print("The (0,0) gcd is zero by software convention; it has no positive greatest common divisor.")

252 = 2*105 + 42
105 = 2*42 + 21
42 = 2*21 + 0
Last nonzero remainder / gcd: 21
a=252, b=105: gcd=21, x=-2, y=5; a*x+b*y=21
a=12, b=18: gcd=6, x=-1, y=1; a*x+b*y=6
a=0, b=7: gcd=7, x=0, y=1; a*x+b*y=7
a=9, b=0: gcd=9, x=1, y=0; a*x+b*y=9
a=0, b=0: gcd=0, x=1, y=0; a*x+b*y=0
The (0,0) gcd is zero by software convention; it has no positive greatest common divisor.

实验 B 重复平方与操作计数

预测：3¹³ mod7 与四个循环头。运行：与三参数 pow 比，包括零指数、负基。解释：百万指数为何二十迭代，以及为何不代表长整数乘法恒成本。修改：跳最后无用平方，保持不变式与输出，比精确乘次数。零基零指数按空积；非负指数限制比完整 Python pow 接口窄。

下载 lab2_modular_powers.py

"""Repeated squaring with exact integer arithmetic and an explicit operation count."""
def power_mod(base, exponent, modulus):
    if exponent < 0 or modulus < 2:
        raise ValueError("Require exponent >= 0 and modulus >= 2")
    original_base, original_exponent = base, exponent
    result, base = 1, base % modulus
    steps, multiplications, trace = 0, 0, []
    while exponent:
        trace.append((result, base, exponent))
        if exponent % 2:
            result = result * base % modulus
            multiplications += 1
        base = base * base % modulus  # Also counted in the final iteration.
        multiplications += 1
        exponent //= 2
        steps += 1
    assert result == pow(original_base, original_exponent, modulus)
    return result, steps, multiplications, trace

for base, exponent, modulus in [(3, 13, 7), (5, 0, 11), (0, 0, 7), (-2, 9, 13), (17, 1_000_000, 97)]:
    value, steps, multiplications, trace = power_mod(base, exponent, modulus)
    assert steps == exponent.bit_length()
    print(f"({base})^{exponent} mod {modulus} = {value}; iterations={steps}, multiplications={multiplications}")
    if (base, exponent, modulus) == (3, 13, 7):
        print("Loop-head (result, base, exponent):", trace)
print("At most two modular multiplications per iteration; their bit cost is not constant in general.")
for base, exponent, modulus in [(3, -1, 7), (3, 5, 1)]:
    try:
        power_mod(base, exponent, modulus)
    except ValueError as error:
        print("Rejected:", (base, exponent, modulus), str(error))

(3)^13 mod 7 = 3; iterations=4, multiplications=7
Loop-head (result, base, exponent): [(1, 3, 13), (3, 2, 6), (3, 4, 3), (5, 2, 1)]
(5)^0 mod 11 = 1; iterations=0, multiplications=0
(0)^0 mod 7 = 1; iterations=0, multiplications=0
(-2)^9 mod 13 = 8; iterations=4, multiplications=6
(17)^1000000 mod 97 = 35; iterations=20, multiplications=27
At most two modular multiplications per iteration; their bit cost is not constant in general.
Rejected: (3, -1, 7) Require exponent >= 0 and modulus >= 2
Rejected: (3, 5, 1) Require exponent >= 0 and modulus >= 2

实验 C 非法除法与校验和碰撞

预测：逆存在、4x≡2 mod6 解与碰撞输出。运行：看拒绝逆与六类穷举解。解释：gcd 逆条件为定理，而有限枚举只查特定方程。修改：校验和换模十一，构造新的允许字节碰撞。更大输出范围不把求和变安全构造。

下载 lab3_division_and_collisions.py

"""Counterexamples to universal modular division and checksum uniqueness."""
from math import gcd

def inverse(a, modulus):
    if modulus < 2:
        raise ValueError("Require modulus >= 2")
    if gcd(a, modulus) != 1:
        raise ValueError("Residue is not invertible")
    return pow(a, -1, modulus)

for a, modulus in [(3, 7), (2, 6), (5, 6), (0, 7)]:
    try:
        inv = inverse(a, modulus)
        assert a * inv % modulus == 1
        print(f"Inverse of {a} mod {modulus}: {inv}")
    except ValueError as error:
        print(f"Inverse of {a} mod {modulus}: rejected ({error})")
for a, b, modulus in [(4, 2, 6), (2, 1, 6)]:
    solutions = [x for x in range(modulus) if (a * x - b) % modulus == 0]
    assert bool(solutions) == (b % gcd(a, modulus) == 0)
    print(f"{a}x = {b} mod {modulus}: solutions {solutions}")
print("Illegal cancellation:", "2*1 mod 6 =", 2 * 1 % 6, "; 2*4 mod 6 =", 2 * 4 % 6)
assert (2 * 1 - 2 * 4) % 6 == 0 and (1 - 4) % 6 != 0

def checksum(values):
    if any(not isinstance(v, int) or v < 0 or v > 255 for v in values):
        raise ValueError("Values must be bytes")
    return sum(values) % 7

pairs = [([1, 2], [0, 3]), ([1, 2], [2, 1]), ([1, 2], [8, 2])]
for left, right in pairs:
    assert left != right and checksum(left) == checksum(right)
    print("Collision:", left, right, "; checksum =", checksum(left))
print("Different checksum proves a difference; equal checksum does not prove equal input or security.")

Inverse of 3 mod 7: 5
Inverse of 2 mod 6: rejected (Residue is not invertible)
Inverse of 5 mod 6: 5
Inverse of 0 mod 7: rejected (Residue is not invertible)
4x = 2 mod 6: solutions [2, 5]
2x = 1 mod 6: solutions []
Illegal cancellation: 2*1 mod 6 = 2 ; 2*4 mod 6 = 2
Collision: [1, 2] [0, 3] ; checksum = 3
Collision: [1, 2] [2, 1] ; checksum = 3
Collision: [1, 2] [8, 2] ; checksum = 3
Different checksum proves a difference; equal checksum does not prove equal input or security.

1–12 必做，13–14 可选扩展。给域、逆条件和准确模检查，不用无解释除号。

自动评分 1–9，最后书面自评。

读 MIT Mathematics for Computer Science 数论选段。MIT Theory of Numbers 讲义 提供欧几里得、线性同余与 CRT 比较。查 Python pow 文档 三整数参数接口。这些是外部一手阅读，本课例子与必做练习原创。

Python 模负指数要求基与模互素。本重复平方故意接受非负指数、模≥2，不要把受限接口当 Python 全部支持情形。

不看笔记声明商余唯一，证明欧几里得保持与终止，从贝祖推逆。区分类与代表，给错误约去，写费马与 CRT 准确条件。

结业任务：模十找可逆元，解 4x≡6，比此环与域。可逆元 1,3,7,9。除 gcd 二得 2x≡3 mod5，x≡4 mod5，原代表四、九。模十非域，二与五是非零零因子。

前进标准：运算前能说明合法性，并限定小实验结论。线性代数分支从向量、几何与数组形状开始，CS 路线随后回概率。见课程总览的课程与路线。