卡迈克尔数

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

概观

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

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

卡迈克尔数的一个等价的定义在Korselt定理（1899年）出现：一个正合成数 $n$ 是卡迈克尔数，若且唯若 $n$ 无平方数因数且对于所有 $n$ 的质因数 $p$ ， $p-1|n-1$ 。

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

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

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

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

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

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