[科普中国]-卡迈克尔数

卡迈克尔数的定义是对于合数n，如果对于所有正整数b，b和n互素，都有同余式b^(n-1)≡ 1 (mod n)成立，则合数n为Carmichael数。1

2016年物流工人余建春带着自己的五项数学发现登上了浙江大学数学系的讲台，与教授和博士生们“同堂论道”，最具价值的发现是一组“卡迈克尔数”（Carmichael数）的判别准则。

定理介绍每个Carmichael至少是三个不同素数的乘积。如561=3*11*17。

费马小定理(Fermat theorem)：

设p为一素数，对于任意整数a，有a(p-1)≡ 1 (mod p)。

假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p） 假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1

性质卡迈克尔数有至少3个正素因数。如图一是首个k个正素因数的卡迈克尔数，k=3,4,5,...：

如图二是首十个有4个素因数的卡迈克尔数：

费马判定设p为一素数，而a与p互素，则 a^p - a 必为p的倍数。 利用费马小定理，对于给定的整数n，可以设计一个素数判定算法。通过计算d=a^(n-1)mod n来判定整数n的素性。当d不等于1时，n肯定不是素数；当d等于1时，n则很可能是素数。但也存在合数n使得d=a^(n-1)≡1(mod n)。例如，当a=2时，满足d=1的最小合数是n=341。为了提高测试的准确性，我们可以随机地选取多个a对a^(n-1)mod n的结果进行测试。能通过全部a的测试的合数n，被称为Carmichael数，前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中，只有255个Carmichael数。

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

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

1.随机选取整数b，2