卡邁克爾數

在數論上，卡邁克爾數（英語：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.