如何使用费马小定理计算器
费马小定理计算器可选择性地对指数进行化简来计算 a^n mod p。填写三个整数输入框，即可获得余数和计算步骤。
- 输入底数 a — 任意整数（正数或负数均可）。
- 输入指数 n — 非负整数。10^15 这样的大数也能即时计算。
- 输入模数 p — 大于等于 2 的正整数。质数模数可启用完整的费马化简。
- 查看结果 — 费马小定理计算器检验质数性和互质性，在条件满足时化简指数，并显示最终余数。
例如，输入 a=3、n=100、p=7：100 mod 6 = 4，所以 3^100 mod 7 = 3^4 mod 7 = 81 mod 7 = 4。
公式与原理 — 费马小定理计算器
费马小定理计算器基于以下定理：
若 p 为质数且 gcd(a, p) = 1：
a^(p−1) ≡ 1 (mod p)
等价形式：
a^p ≡ a (mod p)
指数化简：
a^n mod p = a^(n mod (p−1)) mod p| 符号 | 含义 |
|---|---|
| a | 底数 |
| n | 指数 |
| p | 质数模数 |
| p−1 | 质数 p 的欧拉函数值（即 φ(p)） |
| n mod (p−1) | 计算中使用的化简后指数 |
为何指数化简有效： 由于 a^(p−1) ≡ 1，乘以 a^(p−1) 不改变结果。因此指数中 (p−1) 的倍数部分可消去，只有余数 n mod (p−1) 有意义。
费马小定理不适用的情况： 若 p 不是质数，或 p 整除 a（即 gcd(a, p) > 1），则不能直接应用该定理。计算器会改用平方乘法算法直接计算。
适用范围与局限
模数 p 必须至少为 2，指数 n 必须为非负整数，所有输入均须为整数。
费马小定理计算器的使用场景
费马小定理计算器适用于数论学习、密码学和竞赛数学等场合：
- 数论课程 — 验证 2^12 mod 13 = 1 是否符合定理，用计算器确认结果。
- RSA 密码学 — 理解公钥加密的数学基础，费马小定理是密钥生成的理论依据。
- 竞赛数学 — 快速计算竞赛题目中出现的大整数模幂。
- 质数直觉 — 对多个底数测试 a^(p-1) mod p = 1，作为启发式质数检验（费马质数检验）。
费马小定理计算器展示每一步计算过程——质数检验、互质性检验、指数化简——是理解费马小定理而非仅获取答案的理想工具。