不超过100000的16个卡迈克尔数简单分析存照

moranhuishou

[color=#DC143C]
不超过100000的16个卡迈克尔数如下: 　　561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361
这些数字，用小定理验证都是“素数”，例如
2^560=1(mod 561)
3^560=1(mod 561)
5^560=1(mod 561)
7^560=1(mod 561)
...
但其实他们都是复合数，如561=3*11*17
所以一般以为，用小定理判定素数不是百分之百可靠。
我们先来分析一下上面的16个数字：其中
能被3，5整除的可以简单剔除
561，1105,2465,10585,,62745,
因为我们可以一眼判定这些数都是合数。还有11个
能被7整除的：
7|1729,7|2821,7|6601,7|8911,7|15841,7|41041,7|52633,7|63973;
其他：
11|75361;13|29341,13|46657，
也就是这些数字都有很小很小的素因子，
我们都可以通过简单的“试除”将之排除。

moranhuishou

[color=#DC143C]并且，这些数字也并不是不可以用小定理验证的：
11^63972=41107(mod 63973)
13^63972=5798(mod 63973)
17^63972=57630(mod 63973)
...
7^52692=45115(mod 52693)
21^52692=45115(mod 52693)
35^52692=45115(mod 52693)
...
7^41040=29316(mod 41041)
11^41040=18656(mod 41041)
21^41040=29316(mod 41041)
...
7^15840=6790(mod 15841)
21^15840=6790(mod 15841)
31^15840=10230(mod 15841)
...
所以，这些数实际上对素性判定的影响也是完全可以排除的。

熊一兵

http://www.baidu.com/s?wd=%BF%A8%C3%D7%D0%AA%B6%FB%CA%FD
http://baike.baidu.com/view/2692465.htm
概观
　　费马小定理说明所有质数都有这个性质。在这方面，卡迈克尔数和质数十分相似，所以它们称为伪质
数。 　　因为这些数的存在，使得费马素性检验变得不可靠。不过，它仍可用于证明一个数是合成数。
另一方面，随着数越来越大，卡米歇尔数变得越来越少，1至10^17有585 355个卡米歇尔数。 　　卡米歇
尔数的一个等价的定义在Korselt定理（1899年）出现：一个正合成数n是卡米歇尔数，当且仅当n无平方
数因子且对于所有n的质因子p，p − 1 | n − 1。 　　这个定理即时说明了所有卡米歇尔数是奇数。 　
　Korselt虽然发现了这些性质，但不能找到例子。1910年罗伯特·丹尼·卡迈克尔找到了第一个兼最小
的有这样性质的数——561。561=3×11×17，无平方数因数，且2|560 ; 10|560 ; 16|560 。 　　之后
的卡迈克尔数：（OEIS:A002997） 　　1105 = 5×13×17 (4 | 1104, 12 | 1104, 16 | 1104)1729 = 7
×13×19 (6 | 1728, 12 | 1728, 18 | 1728)2465 = 5×17×29 (4 | 2464, 16 | 2464, 28 | 2464)
2821 = 7×13×31 (6 | 2820, 12 | 2820, 30 | 2820)6601 = 7×23×41 (6 | 6600, 22 | 6600, 40 |
6600)8911 = 7×19×67 (6 | 8910, 18 | 8910, 66 | 8910)J. Chernick 在1939年证明的一个定理，可
以构造卡米歇尔数的一个子集。 　　对于正整数(6k + 1)(12k + 1)(18k + 1)，若其三个因子都是质数
，它是卡米歇尔数。 　　保罗·艾狄胥猜想有无限个卡米歇尔数，1994年 William Alford 、 Andrew
Granville 及 Carl Pomerance 证明了这个命题。 　　此外，对于足够大的n，1至n之间有至少n^(2/7)
个卡米歇尔数。 　　1992年Löh和Niebuhr找到一些很大的卡米歇尔数，其中一个有1 101 518 个因
子且有多于1.6×10^7个位。
性质
　　卡米歇尔数有至少3个正质因子。以下是首个k个正质因子的卡米歇尔数，k=3,4,5,...：
（OEIS:A006931） 　　k   
3 561 = 3×11×17
4 41041 = 7×11×13×41
5 825265 = 5×7×17×19×73
6 321197185 = 5×19×23×29×37×137
7 5394826801 = 7×13×17×23×31×67×73
8 232250619601 = 7×11×13×17×31×37×73×163
9 9746347772161 = 7×11×13×17×19×31×37×41×641
《概率素数论》有此定理

moranhuishou

这些卡数一点不影响小定理的应用，例如：
7^9746347772160= 5569341584093 （mod9746347772161）
11^9746347772160= 7974284540860 （mod9746347772161）
13^9746347772160= 7497190593971 （mod9746347772161）
17^9746347772160= 5159831173498 （mod9746347772161）
19^9746347772160= 8207450755505（mod9746347772161）
...
初步感觉，前人的结论有误！

moranhuishou

因为这样的数字都是由多个因子组成，数字越大，因子越多，以这些因子或者这些因子的倍数为底，都可以用小定理判定的，而这样的数字很多很多！

moranhuishou

再例如这个：
50619601
以
7,11,14,21,22，26，28，33，35， ...
等等为底，都可以确定这个数是复合数！