🔐数论计算器 - 模幂、模逆元、中国剩余定理与欧拉函数在线计算

如何使用数论计算

1. 1选择要算的内容：模幂、模逆元、中国剩余定理或欧拉函数
2. 2填入整数参数（中国剩余定理按「余数 模数」每行一组）
3. 3读取结果，模逆元与同余方程都带验算或通解

常见问题

为什么算 7^222 mod 13 这么快？

用的是快速幂（平方-乘法）：把指数写成二进制，从高位到低位反复平方，遇到 1 就乘一次底数。222 只有 8 个二进制位，十几次乘法就算完了，不需要真的乘 222 次。

模逆元是什么？什么时候不存在？

满足 a·x ≡ 1 (mod m) 的 x 就是 a 关于模 m 的逆元。只有当 gcd(a, m) = 1（即互质）时才存在，否则工具会直接说明不存在。

中国剩余定理能解什么样的题？

「三三数之剩二，五五数之剩三，七七数之剩二」这类问题：每行写「余数 模数」，工具会给出最小非负解和通解 x = x₀ + Mk。

模数不互质还能用吗？

可以。这时解未必存在，工具会逐对检查相容性：余数之差能被 gcd 整除才有解，否则提示方程组无解；有解时按最小公倍数给出合并结果。

欧拉函数有什么用？

φ(n) 是小于 n 且与 n 互质的数的个数，是欧拉定理 a^φ(n) ≡ 1 (mod n) 的基础，也是 RSA 里选取公私钥指数的关键，n 为质数时 φ(n) = n − 1。