费马小定理通常用来检验一个数是否是素数，是素数的必要非充分条件。

1542 2021-11-05 16:05

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

数论中a和p互素。所以a肯定不是p的倍数。

然而满足费马小定理检验的数未必是素数，这种合数叫做卡迈克尔数（Carmichael Number），最小的卡迈克尔数是561。

由费马小定理可得，若n为素数，则对任意整数b，且b和n互素，都有bn-1(mod n) ≡1。因此，若存在整数b，使得bn-1(mod n)≡1不成立，则n是一个合数。

利用上述结论，对于给定的整数n，可以设计一个素数判定算法。

1.随机选取整数b，2<=b<=n-2，计算d =bn-1 (mod n)。当d不等于1时，n是合数；当d等于1时，n则很可能是素数，对于本次判断来说，判断错误的概率为1/2。

2.如此重复多次，可以将判断错误的概率降低至期望值以下。

但是，上述方法有缺陷。因为Carmichael数的存在，可导致上述算法给出一个错误的判断。

前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中，只有255个Carmichael数。

博客