卡迈克尔数
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在数论上,卡迈克尔数(英语:Carmichael numbers)是正合成数,且使得对于所有跟互质的整数,。
概观
费马小定理说明所有质数都有这个性质。在这方面,卡迈克尔数和质数十分相似,所以它们称为伪质数。
因为这些数的存在,使得费马素性检验变得不可靠。不过,它仍可用于证明一个数是合数。另一方面,随着数越来越大,卡迈克尔数变得越来越少,1至有585 355个卡迈克尔数。
卡迈克尔数的一个等价的定义在Korselt定理(1899年)出现:一个正合成数是卡迈克尔数,若且唯若无平方数因数且对于所有的质因数,。
这个定理即时说明了所有卡迈克尔数是奇数。
Korselt虽然发现了这些性质,但不能找到例子。1910年罗伯特·丹尼·卡迈克尔找到了第一个兼最小的有这样性质的数——561。,无平方数因数,且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年证明的一个定理,可以构造卡迈克尔数的一个子集。
对于正整数或,若其三个因数都是质数,它是卡迈克尔数。
保罗·艾狄胥猜想有无限个卡迈克尔数,1994年 William Alford 、 Andrew Granville 及 Carl Pomerance 证明了这个命题。
此外,对于足够大的,1至之间有至少个卡迈克尔数。
1992年Löh和Niebuhr找到一些很大的卡迈克尔数,其中一个有1 101 518 个因数且有多于个位数。
性质
卡迈克尔数有至少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 |
以下是首十个有4个质因数的卡迈克尔数:(OEIS:A074379)
i | |
---|---|
1 | 41041 = 7×11×13×41 |
2 | 62745 = 3×5×47×89 |
3 | 63973 = 7×13×19×37 |
4 | 75361 = 11×13×17×31 |
5 | 101101 = 7×11×13×101 |
6 | 126217 = 7×13×19×73 |
7 | 172081 = 7×13×31×61 |
8 | 188461 = 7×13×19×109 |
9 | 278545 = 5×17×29×113 |
10 | 340561 = 13×17×23×67 |
更高阶的卡迈克尔数
参考
不完全翻译自英文版。
- Chernick, J. (1935). On Fermat's simple theorem. Bull. Amer. Math. Soc. 45, 269–274.
- Ribenboim, Paolo (1996). The New Book of Prime Number Records.
- Howe, Everett W. (2000). Higher-order Carmichael numbers. Mathematics of Computation 69, 1711–1719. (online version)Archive.is的存档,存档日期2012-07-01
- Löh, Günter and Niebuhr, Wolfgang (1996). A new algorithm for constructing large Carmichael numbers (页面存档备份,存于互联网档案馆)(pdf)
- Korselt (1899). Probleme chinois. L'intermediaire des mathematiciens, 6, 142–143.
- Carmichael, R. D. (1912) On composite numbers P which satisfy the Fermat congruence . Am. Math. Month. 19 22–27.
- Erdős, Paul (1956). On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4, 201 –206.
- Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703–722.