卡邁克爾數：修订间差异

以互动方式浏览历史

←上一版本

删除的内容添加的内容

可视化wikitext

行内

2023年9月18日 (一) 16:40的最新版本

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

@@ 第1行： / 第1行： @@
+{{TA|G1=Math}}
-在[[數論]]上，'''卡邁克爾數'''是正[[合成數]]<math>n</math>，且使得對於所有跟<math>n</math>[[互質]]的整數<math>b</math>，<math>b^{n-1} \equiv 1 \pmod{n}</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個卡邁克爾數。
+因為這些數的存在，使得[[费马素性检验]]變得不可靠。不過，它仍可用於證明一個數是[[合數]]。另一方面，隨着數越來越大，卡邁克爾數變得越來越少，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定理（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 。
+Korselt雖然發現了這些性質，但不能找到例子。1910年[[羅伯特·丹尼·卡邁克爾]]找到了第一個兼最小的有這樣性質的數——561。<math>561 = 3 \times 11 \times 17</math>，無平方数因数，且2|560 ; 10|560 ; 16|560 。
 之後的卡邁克爾數：（[[OEIS:A002997]]）
+= 5×13×17 (4 | 1104, 12 | 1104, 16 | 1104)
-<pre>
-= 5&times;13&times;17 (4 | 1104, 12 | 1104, 16 | 1104)
+ [[1729]] = 7×13×19 (6 | 1728, 12 | 1728, 18 | 1728)
-[[1729]] = 7&times;13&times;19 (6 | 1728, 12 | 1728, 18 | 1728)
+= 5×17×29 (4 | 2464, 16 | 2464, 28 | 2464)
-= 5&times;17&times;29 (4 | 2464, 16 | 2464, 28 | 2464)
+= 7×13×31 (6 | 2820, 12 | 2820, 30 | 2820)
-= 7&times;13&times;31 (6 | 2820, 12 | 2820, 30 | 2820)
+= 7×23×41 (6 | 6600, 22 | 6600, 40 | 6600)
-= 7&times;23&times;41 (6 | 6600, 22 | 6600, 40 | 6600)
+= 7×19×67 (6 | 8910, 18 | 8910, 66 | 8910)
-= 7&times;19&times;67 (6 | 8910, 18 | 8910, 66 | 8910)
-</pre>
-J. Chernick 在[[1939年]]證明的一個定理，可以構造卡邁克爾數的一個[[子集]]。
+J. Chernick 在1939年證明的一個定理，可以構造卡邁克爾數的一個[[子集]]。
-對於正整數<math>(6k+1)(12k+1)(18k+1)</math>，若其三個因數都是質數，它是卡邁克爾數。
+對於正整數<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 證明了這個命題。
+[[保羅·艾狄胥]]猜想有無限個卡邁克爾數，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>個位。
+年Löh和Niebuhr找到一些很大的卡邁克爾數，其中一個有1 101 518 個因數且有多於<math>1.6 \times 10^7</math>個位數。
-===性質===
+=== 性質 ===
 卡邁克爾數有至少3個正質因數。以下是首個''k''個正質因數的卡邁克爾數，''k''=3,4,5,...：（[[OEIS:A006931]]）
@@ 第40行： / 第39行： @@
 !''k'' !!&nbsp;
 |-
-|3 ||561 = 3&times;11&times;17
+|3 ||561 = 3×11×17
 |-
-|4 ||41041 = 7&times;11&times;13&times;41
+|4 ||41041 = 7×11×13×41
 |-
-|5 ||825265 = 5&times;7&times;17&times;19&times;73
+|5 ||825265 = 5×7×17×19×73
 |-
-|6 ||321197185 = 5&times;19&times;23&times;29&times;37&times;137
+|6 ||321197185 = 5×19×23×29×37×137
 |-
-|7 ||5394826801 = 7&times;13&times;17&times;23&times;31&times;67&times;73
+|7 ||5394826801 = 7×13×17×23×31×67×73
 |-
-|8 ||232250619601 = 7&times;11&times;13&times;17&times;31&times;37&times;73&times;163
+|8 ||232250619601 = 7×11×13×17×31×37×73×163
 |-
-|9 ||9746347772161 = 7&times;11&times;13&times;17&times;19&times;31&times;37&times;41&times;641
+|9 ||9746347772161 = 7×11×13×17×19×31×37×41×641
 |}
@@ 第61行： / 第60行： @@
 !''i'' !!&nbsp;
 |-
-|1||41041 = 7&times;11&times;13&times;41
+|1||41041 = 7×11×13×41
 |-
-|2|| 62745 = 3&times;5&times;47&times;89
+|2|| 62745 = 3×5×47×89
 |-
-|3||63973 = 7&times;13&times;19&times;37
+|3||63973 = 7×13×19×37
 |-
-|4||75361 = 11&times;13&times;17&times;31
+|4||75361 = 11×13×17×31
 |-
-|5||101101 = 7&times;11&times;13&times;101
+|5||101101 = 7×11×13×101
 |-
-|6||126217 = 7&times;13&times;19&times;73
+|6||126217 = 7×13×19×73
 |-
-|7||172081 = 7&times;13&times;31&times;61
+|7||172081 = 7×13×31×61
 |-
-|8||188461 = 7&times;13&times;19&times;109
+|8||188461 = 7×13×19×109
 |-
-|9||278545 = 5&times;17&times;29&times;113
+|9||278545 = 5×17×29×113
 |-
-|10||340561 = 13&times;17&times;23&times;67
+|10||340561 = 13×17×23×67
 |}
-==更高階的卡邁克爾數==
+== 更高階的卡邁克爾數 ==
 ==參考==
 不完全翻譯自英文版。
-* Chernick, J. (1935). On Fermat's simple theorem. ''Bull. Amer. Math. Soc.'' '''45''', 269&ndash;274.
+* 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&ndash;1719. [http://arxiv.org/abs/math.NT/9812089 (online version)]
+* 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''](pdf)
+* 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&ndash;143.
+* 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&ndash;27.
+* 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&#337;s, Paul (1956). On pseudoprimes and Carmichael numbers, ''Publ. Math. Debrecen'' '''4''', 201 &ndash;206.
+* 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&ndash;722.
+* Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, ''Ann. of Math.'' '''140'''(3), 703–722.
-[[Category:數論]]
+[[Category:同余]]
+[[Category:整数数列|K]]
+[[Category:伪素数]]
-[[de:Carmichael-Zahl]]
-[[en:Carmichael number]]
-[[es:Números de Carmichael]]
-[[fi:Carmichaelin luku]]
-[[fr:Nombre de Carmichaël]]
-[[ko:카마이클 수]]
-[[pl:Liczby Carmichaela]]
-[[pt:Número de Carmichael]]
-[[sl:Carmichaelovo število]]