费马小定理计算器

费马小定理将质数、幂和模运算联系起来。标准形式指出：若 p 为质数且 a 不能被 p 整除，则 a^(p - 1) 除以 p 的余数为 1。用同余记号表示，即 a^(p - 1) 与 1 模 p 同余。当 a = 2、p = 7 时，计算得 2^6 = 64，而 64 除以 7 的余数为 1。 等价形式指出：当 p 为质数时，对任意整数 a，a^p 与 a 模 p 同余。这个版本也涵盖 p 整除 a 的情况，因为此时两边的余数都是零。标准形式要求 a 与 p 的最大公因数为 1。计算器会先检查质数条件和互质条件，再计算所选同余式。 直接计算大整数幂可能产生极其庞大的中间数值。因此，本工具使用二进制模幂算法，也称重复平方法：不断对当前底数平方，并在每次乘法后对 p 取模。这样既保留精确余数，又避免计算难以处理的完整幂值，所需步骤数还仅随指数呈对数增长。该方法是实用密码软件的基础算法。 该定理可用于证明一个数是合数：如果互质底数不满足同余式，那么候选模数就不可能是质数。但通过一次费马测试并不能证明是质数。某些合数在特定底数下也能通过，卡迈克尔数更能对所有与其互质的底数通过标准测试。因此，可靠的素性检测需要更强的确定性检查，或使用精心选择底数的 Miller-Rabin 等测试。 费马的结论支持数论与计算领域的多种应用。它有助于简化模运算中的指数，启发素性测试，并为公钥密码学提供数学基础。RSA 更直接依赖相关的欧拉定理，但费马小定理解释了其中核心的质数模数行为。当 p 为质数且 a 模 p 非零时，也可通过 a^(p - 2) 模 p 求出模逆元。 请使用本计算器验证课堂例题、探索模运算规律，而不是认证大型密码学质数。输入限制为 JavaScript 安全整数，以保证可靠的素性检查；模幂运算本身使用精确整数运算。成功结果表示所选质数和底数满足选定形式，并不能单独证明未经检查的合数候选值是质数。