历史

  皮埃尔·德·费马

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”的论文集，其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。

有些数学家独立制作相关的假说（有时也被错误地称为中国的假说），当 2 p ≡ ≡ --> 2 ( mod p ) {\displaystyle 2^{p}\equiv 2{\pmod {p}}} 成立时，p是质数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如， 2 341 ≡ ≡ --> 2 ( mod 341 ) {\displaystyle 2^{341}\equiv 2{\pmod {341}}} ，而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。

卡迈克尔数

如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

更极端的反例是卡迈克尔数： 假设 a {\displaystyle a} 与561互质，则 a 560 {\displaystyle a^{560}} 被561除都余1。这样的数被称为卡迈克尔数数，561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义，但直到1910年才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。

证明

方法一

若n不能整除 a − − --> b {\displaystyle a-b} ， x > 0 {\displaystyle x>0} ， ( x , n ) = 1 {\displaystyle (x,n)=1} ，则n也不能整除 x ( a − − --> b ) {\displaystyle x(a-b)} 。取整数集 A {\displaystyle A} 为所有小于 p {\displaystyle p} 的集（ A {\displaystyle A} 构成 p {\displaystyle p} 的完全剩余系，即 A {\displaystyle A} 中不存在两个数同余 p {\displaystyle p} ）， B {\displaystyle B} 是 A {\displaystyle A} 中所有的元素乘以a组成的集合。因为 A {\displaystyle A} 中的任何两个元素之差都不能被p整除，所以B中的任何两个元素之差也不能被p整除。

换句话说， g c d ( a , p ) = 1 {\displaystyle gcd(a,p)=1} ，考虑 1 ∗ ∗ --> a , 2 ∗ ∗ --> a , 3 ∗ ∗ --> a , . . . . ( p − − --> 1 ) ∗ ∗ --> a {\displaystyle 1*a,2*a,3*a,....(p-1)*a} 共 ( p − − --> 1 ) {\displaystyle (p-1)} 个数，将它们分别除以p，余数分别为 r 1 , r 2 , r 3 , . . . . , r p − − --> 1 {\displaystyle r_{1},r_{2},r_{3},....,r_{p-1}} ，则集合{r1,r2,r3,...,rp-1}为集合{1,2,3,...,(p-1)}的重新排列，即1,2,3,....,(p-1)在余数中恰好各出现一次；这是因为对于任两个相异k*a而言（k=1,2,3....(p-1)），其差不是p的倍数（所以不会有相同余数），且任一个k*a亦不为p的倍数（所以余数不为0）。因此

即

在这里W=1·2·3·...·(p-1)，且(W, p) = 1，因此将整个公式除以W即得到：

方法二

考虑二项式系数 ( p n ) = p ! n ! ( p − − --> n ) ! {\displaystyle {\tbinom {p}{n}}={\tfrac {p!}{n!(p-n)!}}} ，n不为p或0，由于分子有质数p，但分母不含p，故分子的p能保留，不被约分而除去，即 ( p n ) {\displaystyle {\tbinom {p}{n}}} 恒为p的倍数。

再考虑(b+1)的二项式展开，模p，则

因此

令b=a-1，即得 a p ≡ ≡ --> a ( mod p ) {\displaystyle a^{p}\equiv a{\pmod {p}}} 。

应用

计算 2 100 {\displaystyle 2^{100}} 除以13的余数

故余数为3。

证明对于任意整数a而言， a 13 − − --> a {\displaystyle a^{13}-a} 恒为2730的倍数。13减1为12，12的正因数有1, 2, 3, 4, 6, 12，分别加1，为2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13为质数，根据定理， a 13 − − --> a {\displaystyle a^{13}-a} 为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数，即2*3*5*7*13=2730的倍数。

推广

欧拉定理

费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公约数是1，那么

这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互质的数的个数。假如n是一个素数，则φ(n) = n-1，即费马小定理。

卡迈克尔函数

卡迈克尔函数比欧拉函数更小。费马小定理也是它的特殊情况。

多项式除法

p | x p − − --> x ⇒ ⇒ --> p k | ( x p − − --> x ) k {\displaystyle p|x^{p}-x\Rightarrow p^{k}|(x^{p}-x)^{k}}

除式： x p k ≡ ≡ --> ∑ ∑ --> i = 1 k ( − − --> 1 ) i − − --> 1 ( k i ) x p k − − --> ( p − − --> 1 ) i ( mod p k ) {\displaystyle \displaystyle x^{pk}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}x^{pk-(p-1)i}{\pmod {p^{k}}}}

余式： x p k + ( p − − --> 1 ) n ≡ ≡ --> ∑ ∑ --> i = 1 k ( − − --> 1 ) i − − --> 1 ( n + i − − --> 1 i − − --> 1 ) ( n + k k − − --> i ) x p k − − --> ( p − − --> 1 ) i ( mod p k ) {\displaystyle \displaystyle x^{pk+(p-1)n}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {n+i-1}{i-1}}{\binom {n+k}{k-i}}x^{pk-(p-1)i}{\pmod {p^{k}}}}

n=0时为除式，用数学归纳法证明余式。

x 10 + 4 n ≡ ≡ --> ( n + 2 ) x 6 − − --> ( n + 1 ) x 2 ( mod 5 2 ) {\displaystyle x^{10+4n}\equiv (n+2)x^{6}-(n+1)x^{2}{\pmod {5^{2}}}}

x 1000 ≡ ≡ --> 249 x 8 − − --> 248 x 4 ≡ ≡ --> 24 x 8 − − --> 23 x 4 ( mod 5 2 ) {\displaystyle x^{1000}\equiv 249x^{8}-248x^{4}\equiv 24x^{8}-23x^{4}{\pmod {5^{2}}}}

Python程式码

1 >>>n=221 2 >>>a=38 3 >>>pow(a,n-1,n) 4 1 5 6 """221 may be a prime number.""" 7 8 importrandom 9 defisprime(n,k=128):10 ifn<2:11 returnFalse12 for_inrange(k):13 a=random.randrange(1,n)14 ifpow(a,n-1,n)!=1:15 returnFalse16 returnTrue

参见

费马大定理

拉格朗日定理

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。