SuperAPI AI 工具集

solve-modular-arithmetic

通用与其它

查看项目

更新于 10-16 03:42

技能介绍

用途:求解模算术问题。主要能力包括:解析并规范化单个线性同余方程 ax≡b (mod m)、同余方程组(中国剩余定理)、模逆元 a^{-1} (mod m)、模幂 a^k (mod m) 及元素阶的判定。

使用方式:按步骤执行——先解析并归一化问题;单个同余用扩展欧几里得算法求解,先检查 gcd(a,m) 是否整除 b,再约简并求逆;方程组先验证模数两两互素(否则检查相容性),再用中国剩余定理 x=Σ(ai·Mi·yi) mod M 求唯一解;模幂用欧拉定理 a^{phi(m)}≡1 (mod m)(要求 gcd(a,m)=1)或费马小定理约简指数,并用重复平方计算;最后代入原方程验证每个解。

适用场景:同余方程、同余方程组、模逆元、大指数模幂、循环群与素根相关计算。

限制:模数非两两互素时标准中国剩余定理公式不适用,需先判断相容性;gcd(a,m)>1 时不能直接使用欧拉定理;Mi 的逆元须对 mi 而非 M 取模;扩展欧几里得回代需注意符号;模幂每步都要取模以防溢出。资料另给出欧拉函数参考值表和常见陷阱,未提供命令行安装或运行方式。