卡邁克爾數

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

以下是首十個有4個質因數的卡邁克爾數：（OEIS:A074379）

不完全翻譯自英文版。

• 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 ${\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.