免费费马小定理计算器

理解费马小定理

费马小定理是初等数论的基石，建立了素数与模运算之间的深刻联系。该定理指出，如果 $p$ 是素数且 $a$ 是任意整数，则 $a^{p} - a$ 总是可被 $p$ 整除。使用模运算的语言，我们写作：

$$a^{p} \equiv a \pmod{p}$$

当 $a$ 不是 $p$ 的倍数时（即 $\gcd(a,p)=1$），定理可简化为：

$$a^{p-1} \equiv 1 \pmod{p}$$

这一结果是许多应用的基础：素数测试、公钥密码学（如RSA）以及计算模逆元。虽然素数定理描述了素数的渐近分布，但费马小定理提供了具体的关系，驱动着许多现代算法。基于费马小定理的模运算计算器可帮助您快速验证这些同余式。

示例演示

让我们检查两个具体案例，看看定理在不同条件下的表现。

情况 1：$a$ 与 $p$ 互质。 取 $p=7$ 和 $a=15$。由于15不能被7整除，适用简化版本：

$$15^{6} \equiv 1 \pmod{7}$$

计算：$15^{6} = 11,390,625$；减1得到 $11,390,624$，等于 $7 \times 1,627,232$，证实可整除。

情况 2：$a$ 被 $p$ 整除。 现在考虑 $p=7$ 和 $a=14$。这里14是7的倍数，因此我们必须使用原始形式：

$$14^{7} \equiv 14 \pmod{7}$$

实际上，$14^{7} - 14 = 105,413,504$ 恰好等于 $7 \times 15,059,070$，满足同余式。

这些例子说明了在应用简化指数形式之前检查互质条件的重要性。

如何使用费马小定理计算器

在线费马小定理计算器——一个专用的模计算器——简化了应用该定理的过程。使用步骤：

1. 输入两个整数 $a$ 和 $p$。
2. 工具首先验证 $p$ 是否为素数（您也可以提前使用素数检查器进行检查）。
3. 然后检查 $a$ 与 $p$ 是否互质。
4. 根据这些检查，它显示适当的定理版本并展示结果同余式。

这个模计算器在快速验证模关系和教学方面特别有用。

求模 $p$ 的乘法逆元

费马小定理的一个重要应用是计算整数模素数的乘法逆元。由 $a^{p-1} \equiv 1 \pmod{p}$ 可得 $a \cdot a^{p-2} \equiv 1 \pmod{p}$。因此，$a$ 模 $p$ 的逆元是 $a^{p-2}$。计算器可以高效地计算模 $p$ 幂运算，无需复杂计算即可提供模逆元。

利用定理进行素数测试

费马小定理还提供了一种概率性素数测试法。要测试一个数 $p$ 是否为素数：

• 选择一个介于2和 $p-2$ 之间的随机整数 $a$，满足 $\gcd(a,p)=1$。
• 计算 $a^{p-1} \bmod p$。
• 如果结果不等于1，则 $p$ 一定是合数。
• 如果结果等于1，测试不确定；换一个不同的 $a$。
• 在经过多次成功测试后，$p$ 被认为是“可能素数”。

虽然该测试不能保证素数性（某些合数，称为卡迈克尔数，可能始终通过测试），但它提供了一种快速检查方法。结合其他测试，它构成了许多现代素数检查的基础。

历史视角

费马在1640年写给弗雷尼克·德·贝西的一封信中首次陈述了他的“小定理”，但他没有提供证明。第一个公开发表的证明由欧拉于1736年给出，尽管莱布尼茨更早独立发现。该定理被冠以“小”的昵称，以区别于费马大定理，后者涉及方程 $x^{n} + y^{n} = z^{n}$，并于1995年由安德鲁·怀尔斯最终证明。尽管名字谦逊，费马小定理仍然是数论和现代密码学中的重要工具。

结论

费马小定理计算器为探索同余式以及在各种场景中应用该定理提供了便捷途径，从寻找模逆元到素数测试。通过理解其陈述和条件，您可以在理论和实践环境中充分利用这一强大结果。