费马小定理与威尔逊定理
你是否想过,不用一个个试除,就能快速判断一个数是不是质数?或者,你知道为什么某些加密算法(比如RSA)能保证你的密码安全?这背后藏着两个神奇的“数学魔法”——费马小定理和威尔逊定理。它们就像数论世界的“超能力”,一个用分糖果的故事让你记住,一个用排队游戏让你理解。下面我们就边玩边学,再用C++代码亲手验证这些魔法。
1. 费马小定理:分糖果的“剩一颗”规律
核心思想:当你有一堆糖果(数量为 aaa),想分给 ppp 个小朋友(ppp 必须是质数),而且 aaa 不能被 ppp 整除(也就是每人分不到整数颗)。那么,如果你把糖果数量取 aaa 的 p−1p-1p−1 次方,再除以 ppp,余数一定是 1!
用数学语言说: 若 ppp 是质数,且 gcd(a,p)=1\gcd(a, p) = 1gcd(a,p)=1(即 aaa 与 ppp 互质),则
ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp)
举个具体例子
- 小朋友人数 p=7p = 7p=7(质数),糖果数 a=2a = 2a=2(2 不能被 7 整除)。 计算 27−1=26=642^{7-1} = 2^6 = 6427−1=26=64,64 ÷ 7 = 9 余 1。果然余数为 1!
- 试试 p=5p = 5p=5,a=3a = 3a=3:34=813^{4} = 8134=81,81 ÷ 5 = 16 余 1。
- 再试试 p=11p = 11p=11,a=5a = 5a=5:510=97656255^{10} = 9765625510=9765625,除以 11 的余数是多少?用计算机算一下,也是 1!
为什么说它是“魔法”?
因为当 ppp 很大时,直接计算 ap−1a^{p-1}ap−1 会得到一个天文数字。但我们只需要余数,可以用快速幂(模运算)在电脑上瞬间算出来。这个特性被广泛用于:
- 快速判断质数(但不完美,见后文)
- RSA加密:RSA 的安全性基于大数分解的困难,而加密/解密过程要用到费马小定理的推广——欧拉定理。
- 求乘法逆元:如果想找一个数 xxx 使得 a⋅x≡1(modp)a \cdot x \equiv 1 \pmod{p}a⋅x≡1(modp),那么 x≡ap−2(modp)x \equiv a^{p-2} \pmod{p}x≡ap−2(modp)(因为 a⋅ap−2=ap−1≡1a \cdot a^{p-2} = a^{p-1} \equiv 1a⋅ap−2=ap−1≡1)。这在竞赛中经常用到。
2. 威尔逊定理:排队游戏的“循环节”秘密
核心思想:让 ppp 个小朋友按编号 1, 2, 3, …, p−1p-1p−1 排成一圈,把他们的编号全部乘起来,得到 (p−1)!(p-1)!(p−1)!。然后给这个乘积加上 1,问:加上 1 后的数能否被 ppp 整除?只有 ppp 是质数时,这个规律才成立。
用数学语言: ppp 是质数 当且仅当 (p−1)!+1≡0(modp)(p-1)! + 1 \equiv 0 \pmod{p}(p−1)!+1≡0(modp)。 换句话说,(p−1)!≡−1(modp)(p-1)! \equiv -1 \pmod{p}(p−1)!≡−1(modp)。
举个例子
- p=5p = 5p=5:(5−1)!=4!=24(5-1)! = 4! = 24(5−1)!=4!=24,24+1=2524 + 1 = 2524+1=25,25 ÷ 5 = 5,余数为 0,所以 5 是质数。
- p=7p = 7p=7:6!=7206! = 7206!=720,720 + 1 = 721,721 ÷ 7 = 103,整除,所以 7 是质数。
- 反例:p=4p = 4p=4(合数):(4−1)!=3!=6(4-1)! = 3! = 6(4−1)!=3!=6,6 + 1 = 7,7 ÷ 4 余 3,不是 0,说明 4 不是质数。
- 再试 p=6p = 6p=6:5!=1205! = 1205!=120,120 + 1 = 121,121 ÷ 6 余 1,不是 0。
为什么叫“排队游戏”?
想象小朋友们按顺序排成一圈,你会发现在质数的情况下,除了 1 和 p−1p-1p−1 这两个“特殊小朋友”,其他小朋友都能两两配对,使得乘积模 ppp 余 1(比如 2 × 3 = 6 ≡ 1 mod 5)。最后剩下的 1 和 p−1p-1p−1 乘起来是 p−1p-1p−1,相当于 −1-1−1。所以整个乘积就是 −1-1−1 模 ppp。把这个故事编成程序,就能用来验证质数。
3. 新手容易犯的错误
错误1:以为费马小定理的逆命题一定成立
很多同学觉得:如果 ap−1≡1(modp)a^{p-1} \equiv 1 \pmod{p}ap−1≡1(modp),那么 ppp 一定是质数。这是错的! 有一些合数也能“骗过”这个测试,比如 p=341p = 341p=341(341 = 11 × 31),取 a=2a = 2a=2,你会发现 2340≡1(mod341)2^{340} \equiv 1 \pmod{341}2340≡1(mod341),但 341 是合数。这种合数叫 伪质数(Fermat pseudoprime)。所以费马小定理只能作为“可能是质数”的依据,不能100%确定。
错误2:忽略“a 和 p 互质”的条件
如果 aaa 能被 ppp 整除(比如 a=7,p=7a = 7, p = 7a=7,p=7),那么 ap−1≡0(modp)a^{p-1} \equiv 0 \pmod{p}ap−1≡0(modp),而不是 1。所以使用费马小定理前,要确保 gcd(a,p)=1\gcd(a,p)=1gcd(a,p)=1。
错误3:直接计算大阶乘
威尔逊定理虽然优美,但计算 (p−1)!(p-1)!(p−1)! 对于大 ppp 极其耗时(需要 p−1p-1p−1 次乘法),所以不能用来判断大质数。它更多用于理论证明和极小的质数验证。
4. 用 C++ 完整验证两个定理
下面我们写一段完整的程序,既用费马小定理做素性检验(注意它只能检测“可能是质数”),又用威尔逊定理真实验证小质数。为了直观,我们让用户输入一个数,然后分别用两种方法检查。
#include <iostream>
using namespace std;
// 快速幂函数:计算 a 的 b 次方模 m
long long pow_mod(long long a, long long b, long long m) {
long long res = 1; // 结果,初始为 1
while (b > 0) {
if (b & 1) { // 如果当前二进制位是 1
res = res * a % m; // 乘上 a 并取模
}
a = a * a % m; // a 平方并取模
b >>= 1; // b 右移一位
}
return res;
}
// 用费马小定理做素性检验(底数选 2 和 3,降低被伪质数欺骗的概率)
bool fermat_test(long long p) {
if (p < 2) return false; // 小于 2 不是质数
if (p == 2 || p == 3) return true; // 2 和 3 是质数
// 用两个底数 a = 2 和 a = 3 测试(对大多数小数足够)
if (pow_mod(2, p - 1, p) != 1) return false;
if (pow_mod(3, p - 1, p) != 1) return false;
return true; // 通过两个测试,可能是质数
}
// 用威尔逊定理验证质数(仅适合小 p)
bool wilson_test(long long p) {
if (p < 2) return false;
long long factorial = 1; // 存储 (p-1)!
for (long long i = 1; i < p; ++i) {
factorial = factorial * i % p; // 边乘边取模,避免溢出
}
// 威尔逊定理:(p-1)! ≡ -1 mod p 即 (p-1)! + 1 能被 p 整除
return (factorial + 1) % p == 0;
}
int main() {
long long n;
cout << "请输入一个整数(不超过 10 万,否则威尔逊定理会非常慢):";
cin >> n;
// 费马检验
bool fermat_result = fermat_test(n);
cout << "费马小定理检验(底数2和3):";
if (fermat_result)
cout << n << " 可能是质数(注意可能有伪质数)" << endl;
else
cout << n << " 一定是合数" << endl;
// 威尔逊检验(谨慎使用,n 太大时会卡死)
if (n <= 10000) { // 只对小范围使用,避免长时间计算
bool wilson_result = wilson_test(n);
cout << "威尔逊定理检验:";
if (wilson_result)
cout << n << " 是质数(威尔逊定理准确)" << endl;
else
cout << n << " 是合数" << endl;
} else {
cout << "n 太大,不进行威尔逊检验(计算太慢)" << endl;
}
return 0;
}
运行示例:
请输入一个整数(不超过 10 万,否则威尔逊定理会非常慢):7
费马小定理检验(底数2和3):7 可能是质数(注意可能有伪质数)
威尔逊定理检验:7 是质数(威尔逊定理准确)
请输入一个整数:341
费马小定理检验(底数2和3):341 可能是质数(注意可能有伪质数)
威尔逊定理检验:341 是合数
你看,对于 341(等于 11×31),费马检验误判了(因为 2340≡1mod 3412^{340} \equiv 1 \mod 3412340≡1mod341),而威尔逊定理正确识别它是合数。所以不要完全依赖费马小定理,但如果改用多个底数(比如 Miller–Rabin 检验),准确性会大大提高。
5. 相关知识点指引
- 欧拉定理:费马小定理的推广,当模数不是质数时,aφ(n)≡1(modn)a^{\varphi(n)} \equiv 1 \pmod{n}aφ(n)≡1(modn),其中 φ(n)\varphi(n)φ(n) 是欧拉函数。RSA 加密的核心就是这个。
- Miller–Rabin 素性检验:改进了费马检验,用多个底数和二次探测,是目前最常用的概率性素性检验方法(CSP-S 可能会考)。
- 乘法逆元:利用费马小定理求模质数下的逆元,是组合数学(如计算大组合数取模)的必备技能。
- 中国剩余定理:另一个经典的数论工具,常与费马小定理结合解题。
这两个定理就像数论世界的“两块积木”,掌握了它们,你就能搭建更复杂的数学城堡。下次遇到判断质数、加密解密、求解同余方程的问题,别忘了这些神奇的“魔法”哦!