卡迈克尔数

在数论上，卡迈克尔数（英语：Carmichael numbers）是正合成数${\displaystyle n}$，且使得对于所有跟${\displaystyle n}$互素的整数${\displaystyle b}$，${\displaystyle b^{n-1}\equiv 1{\pmod {n}}}$。

概观

费马小定理说明所有素数都有这个性质。在这方面，卡迈克尔数和素数十分相似，所以它们称为伪素数。

因为这些数的存在，使得费马素性检验变得不可靠。不过，它仍可用于证明一个数是合数。另一方面，随着数越来越大，卡迈克尔数变得越来越少，1至${\displaystyle 10^{17}}$有585 355个卡迈克尔数。

卡迈克尔数的一个等价的定义在Korselt定理（1899年）出现：一个正合成数${\displaystyle n}$是卡迈克尔数，当且仅当${\displaystyle n}$无平方数约数且对于所有${\displaystyle n}$的素因数${\displaystyle p}$，${\displaystyle p-1|n-1}$。

这个定理即时说明了所有卡迈克尔数是奇数。

Korselt虽然发现了这些性质，但不能找到例子。1910年罗伯特·丹尼·卡迈克尔找到了第一个兼最小的有这样性质的数——561。${\displaystyle 561=3\times 11\times 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年证明的一个定理，可以构造卡迈克尔数的一个子集。

对于正整数${\displaystyle (6k+1)(12k+1)(18k+1)}$或${\displaystyle (6k+1)(18k+1)(54k^{2}+12k+1)}$，若其三个约数都是素数，它是卡迈克尔数。

保罗·埃尔德什猜想有无限个卡迈克尔数，1994年 William Alford 、 Andrew Granville 及 Carl Pomerance 证明了这个命题。

此外，对于足够大的${\displaystyle n}$，1至${\displaystyle n}$之间有至少${\displaystyle n^{2/7}}$个卡迈克尔数。

1992年Löh和Niebuhr找到一些很大的卡迈克尔数，其中一个有1 101 518 个约数且有多于${\displaystyle 1.6\times 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

以下是首十个有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.today的存档，存档日期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 ${\displaystyle a^{P-1}\equiv 1{\bmod {P}}}$. 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.