卡邁克爾數

卡邁克爾數

卡邁克爾數（Carmichael numbers）是一種特殊的合數，在數論中具有重要地位。這類數滿足以下性質：對於所有與該數互質的整數b，都能使同餘式b^(n-1) ≡ 1 mod n成立。換句話說，卡邁克爾數是一種「絕對偽素數」，能夠通過所有以與其互質的數為底的費馬素性測試。

卡邁克爾數以美國數學家羅伯特·丹尼·卡邁克爾（Robert Daniel Carmichael）的名字命名，他在1910年首次發現這類數。實際上，最早發現的卡邁克爾數561是由捷克數學家瓦茨拉夫·謝爾賓斯基（Václav Šimerka）在1885年就已發現，但這一發現長期未被數學界所知。

卡邁克爾數具有以下重要數學特性：

1. 無平方因子：卡邁克爾數必須是無平方因子的數，即不能被任何素數的平方整除。

2. 奇數性：所有卡邁克爾數都是奇數。

3. 至少三個素因子：卡邁克爾數必須至少有三個不同的素因子。

4. 特殊整除性：對於卡邁克爾數n的每個素因子p，都有(p-1)整除(n-1)。

最小的卡邁克爾數是561，其分解為3×11×17。其他例子包括：

• 1105 = 5×13×17

• 1729 = 7×13×19

• 2465 = 5×17×29

• 2821 = 7×13×31

卡邁克爾數的構造可以基於Korselt準則：一個無平方因子的合數n是卡邁克爾數，當且僅當對於n的每個素因子p，都有(p-1)整除(n-1)。

卡邁克爾數在自然數中的分布相當稀疏：

1. 無限性：1994年，Alford、Granville和Pomerance證明存在無限多個卡邁克爾數。

2. 密度估計：對於足夠大的x，小於x的卡邁克爾數的數量至少為x^(2/7)。

3. 具體數量：截至2021年，已知小於10^21的卡邁克爾數有20,138,200個。

卡邁克爾數與費馬小定理密切相關。費馬小定理指出，若p是素數，則對所有不被p整除的整數a，有a^(p-1) ≡ 1 mod p。卡邁克爾數正是那些不是素數但滿足類似條件的合數。

卡邁克爾數在密碼學和素性測試中具有重要意義：

1. 密碼學影響：卡邁克爾數的存在意味著費馬素性測試不能完全可靠地檢測素數。

2. 素性測試：現代素性測試如米勒-拉賓測試就是為了解決卡邁克爾數帶來的問題而發展的。

3. 理論研究：卡邁克爾數的研究推動了數論中關於偽素數和強偽素數的研究。

檢測一個數是否為卡邁克爾數可以採用以下方法：

1. Korselt準則：檢查數是否無平方因子，且所有素因子p滿足(p-1)|(n-1)。

2. 因數分解：完全分解數的素因子後驗證上述條件。

3. 快速檢測算法：利用模運算和數論性質設計的專門算法。

數學家還研究了卡邁克爾數的各種變體和推廣：

1. 塔別脫數：一類與卡邁克爾數相關的數，滿足特定形式的構造。

2. 廣義卡邁克爾數：放寬某些條件後的推廣概念。

3. 高階卡邁克爾數：滿足更嚴格條件的卡邁克爾數子類。

卡邁克爾數的研究仍在繼續，它們的神秘性質繼續吸引著數論學家的關注。