费马小定理

费马小定理

费马小定理：如果p是一个素数，而a是任何不能被p整除的整数，那么p能除a - 1。这个由皮埃尔·德·费马在1640年发现的数字性质，本质上是说，取任意素数p和任意不能被该素数整除的数a，假设p = 7, a = 20。通过费马小定理，我们发现：费马小定理通常用来检验一个数是否是素数，是素数的必要非充分条件。然而满足费马小定理检验的数未必是素数，这种合数叫做卡迈克尔数（Carmichael Number），最小的卡迈克尔数是561【A002997】

费马小定理

费尔马小定理即费马小定理。费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。注意事项：由17世纪法国数学家皮耶·德·费玛提出。它断言当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。德国佛尔夫斯克曾宣布以10万马克作为奖金奖给在他逝世后一百年内，第一个证明该定理的人，吸引了不少人尝试并递交他们的“证明”。被提出后，经历多人猜想辩证，历经三百多年的历史，最终在1995年被英国数学家安德鲁·怀尔斯彻底证明。

费马小定理

费马小定理，也称费马定理，是一个数论中的基本定理，是指在模质数下，任取一个不是该质数倍数的整数a，其幂次为p-1时，模质数的结果恒为1，即：a^(p-1)≡ 1 (mod p)其中，p为一个素数，a为任意一个满足1 <= a < p的整数。费马小定理最早由法国数学家费马于17世纪提出，它是欧拉定理和欧拉-费马定理的基础，被广泛应用于密码学、编码、计算机科学等领域。费马小定理的证明可以采用数学归纳法，设k为一个正整数，则有： 当k=1时，a^0 ≡ 1 (mod p)，结论成立。当k>1时，假设a^(p-1) ≡ 1 (mod p)成立，则有：a^(kp-k) ≡ (a^(p-1))^k * a^(-k) ≡ 1^k * a^(-k) ≡ a^(p-1)* a^(-k) ≡ a^(p-1-k) (mod p)因此，当k>1时，a^(kp-k) ≡ a^(p-1-k)(mod p) 成立。 因为p是素数，a是不是p的倍数的整数，所以a和p互质，即它们没有公共因数。由欧拉定理可知，a^(φ(p)) ≡ 1 (mod p)，其中φ(p)表示小于p且与p互质的正整数的个数，因此有φ(p)≤ p-1。根据算术基本定理，p是质数，所以φ(p) = p-1，因此有：a^(p-1) ≡ 1 (mod p)费马小定理的应用非常广泛，其中一个重要的应用领域是密码学。在加密算法中，选择两个大质数p和q，将它们乘积pq作为公共模数，并选择一个整数e作为公钥，使得e与(p-1) *(q-1)互质，然后选择一个整数d作为私钥，使得d*e ≡ 1(mod (p-1) * (q-1))，这样就可以利用费马小定理对加密和解密进行高效的处理。