⚡

模运算Skill modular-arithmetic

这个技能专注于在图形数论中应用模算术解决问题，包括扩展欧几里得算法、中国剩余定理、欧拉定理等关键技术，并利用工具如Sympy和Z3进行计算和证明。关键词：模运算，图数论，问题解决，算法，数学工具。

数据分析 0 次安装 0 次浏览 更新于 3/14/2026

name: 模运算 description: “图数论中模算术问题解决策略” allowed-tools: [Bash, Read]

模运算

何时使用

在图形数论中处理模算术问题时使用此技能。

决策树

  1. 扩展欧几里得算法

    • 找到gcd(a,b)和x,y，使得ax + by = gcd(a,b)
    • 模逆：a^{-1} mod n 当gcd(a,n) = 1时
    • sympy_compute.py solve "a*x == 1 mod n"

  2. 中国剩余定理

    • 系统 x = a_i (mod m_i) 其中m_i互质
    • 唯一解模prod(m_i)
    • z3_solve.py prove "crt_solution_exists"

  3. 欧拉定理

    • a^{phi(n)} = 1 (mod n) 当gcd(a,n) = 1时
    • phi(p^k) = p^{k-1}(p-1)
    • sympy_compute.py simplify "euler_phi"

  4. 二次剩余

    • 勒让德符号：(a/p) = a^{(p-1)/2} mod p
    • 二次互反律：(p/q)(q/p) = (-1)^{…}
    • Tonelli-Shanks算法求平方根

  5. 阶与本原根

    • ord_n(a) = 最小k使得a^k = 1 (mod n)
    • 本原根：ord_n(a) = phi(n)

工具命令

Sympy_Mod_Inverse

uv run python -m runtime.harness scripts/sympy_compute.py solve "a*x == 1 mod n" --var x

Z3_Crt

uv run python -m runtime.harness scripts/z3_solve.py prove "solution_exists_iff_pairwise_coprime"

Sympy_Euler_Phi

uv run python -m runtime.harness scripts/sympy_compute.py simplify "phi(p**k) == p**(k-1)*(p-1)"

Z3_Quadratic_Residue

uv run python -m runtime.harness scripts/z3_solve.py prove "legendre_symbol_multiplicative"

关键技术

摘自索引教科书：

  • [图论（研究生数学教材（173））] 我们用N表示自然数集，包括零。整数模n的集合Z/nZ表示为Zn；其元素写为i := i + nZ。当我们将Z2 = {0, 1}视为域时，也表示为F2 = {0, 1}。

认知工具参考

参见.claude/skills/math-mode/SKILL.md获取完整工具文档。