查看“︁卡邁克爾數”︁的源代码

{{TA|G1=Math}}
在[[數論]]上，'''卡邁克爾數'''（{{lang-en|Carmichael numbers}}）是正[[合成數]]<math>n</math>，且使得對於所有跟<math>n</math>[[互質]]的整數<math>b</math>，<math>b^{n-1} \equiv 1 \pmod{n}</math>。

== 概觀 ==
[[費馬小定理]]說明所有[[質數]]都有這個性質。在這方面，卡邁克爾數和質數十分相似，所以它們稱為[[偽質數]]。

因為這些數的存在，使得[[费马素性检验]]變得不可靠。不過，它仍可用於證明一個數是[[合數]]。另一方面，隨着數越來越大，卡邁克爾數變得越來越少，1至<math>10^{17}</math>有585 355個卡邁克爾數。

卡邁克爾數的一個等價的定義在Korselt定理（1899年）出現：一個正合成數<math>n</math>是卡邁克爾數，[[若且唯若]]<math>n</math>[[無平方數因數]]且對於所有<math>n</math>的[[質因數]]<math>p</math>，<math>p-1|n-1</math>。

這個定理即時說明了所有卡邁克爾數是[[奇數]]。

Korselt雖然發現了這些性質，但不能找到例子。1910年[[羅伯特·丹尼·卡邁克爾]]找到了第一個兼最小的有這樣性質的數——561。<math>561 = 3 \times 11 \times 17</math>，無平方数因数，且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年證明的一個定理，可以構造卡邁克爾數的一個[[子集]]。

對於正整數<math>(6k+1)(12k+1)(18k+1)</math>或<math>(6k+1)(18k+1)(54k^2+12k+1)</math>，若其三個因數都是質數，它是卡邁克爾數。

[[保羅·艾狄胥]]猜想有無限個卡邁克爾數，1994年 William Alford 、 Andrew Granville 及 Carl Pomerance 證明了這個命題。

此外，對於足夠大的<math>n</math>，1至<math>n</math>之間有至少<math>n^{2/7}</math>個卡邁克爾數。

1992年Löh和Niebuhr找到一些很大的卡邁克爾數，其中一個有1 101 518 個因數且有多於<math>1.6 \times 10^7</math>個位數。

=== 性質 ===
卡邁克爾數有至少3個正質因數。以下是首個''k''個正質因數的卡邁克爾數，''k''=3,4,5,...：（[[OEIS:A006931]]）

{| border="1" cellspacing="0" cellpadding="2"
|- 
!''k'' !!&nbsp;
|-
|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]]）

{| border="1" cellspacing="0" cellpadding="2"
|-
!''i'' !!&nbsp;
|-
|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. [http://arxiv.org/abs/math.NT/9812089 (online version)]{{Webarchive|url=https://archive.today/20120701135856/http://arxiv.org/abs/math.NT/9812089 |date=2012-07-01 }}
* Löh, Günter and Niebuhr, Wolfgang (1996). [http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf ''A new algorithm for constructing large Carmichael numbers''] {{Wayback|url=http://www.ams.org/mcom/1996-65-214/S0025-5718-96-00692-8/S0025-5718-96-00692-8.pdf |date=20081008024222 }}(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 <math>a^{P-1}\equiv 1\bmod P</math>. ''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.

[[Category:同余]]
[[Category:整数数列|K]]
[[Category:伪素数]]