卡邁克爾數

費馬小定理(Fermat theorem)：

設p為一素數，對於任意整數a，有a^(p-1)≡ 1 (mod p)。

假如p是質數，且gcd(a,p)=1，那麼 a^(p-1) ≡1（mod p） 假如p是質數，且a,p互質，那麼 a的(p-1)次方除以p的餘數恆等於1

卡邁克爾數有至少3個正素因數。如圖一是首個k個正素因數的卡邁克爾數，k=3,4,5,...：

如圖二是首十個有4個素因數的卡邁克爾數：

設p為一素數，而a與p互素，則 a^p - a 必為p的倍數。 利用費馬小定理，對於給定的整數n，可以設計一個素數判定算法。通過計算d=a^(n-1)mod n來判定整數n的素性。當d不等於1時，n肯定不是素數；當d等於1時，n則很可能是素數。但也存在合數n使得d=a^(n-1)≡1(mod n)。例如，當a=2時，滿足d=1的最小合數是n=341。為了提高測試的準確性，我們可以隨機地選取多個a對a^(n-1)mod n的結果進行測試。能通過全部a的測試的合數n，被稱為Carmichael數，前3個Carmichael數是561,1105,1729。Carmichael數是非常少的。在1~100000000範圍內的整數中，只有255個Carmichael數。

由費馬小定理可得，若n為素數，則對任意整數b，且b和n互素，都有b^n-1(mod n) ≡1。因此，若存在整數b，使得b^n-1(mod n)≡1不成立，則n是一個合數。

利用上述結論，對於給定的整數n，可以設計一個素數判定算法。

1.隨機選取整數b，2<=b<=n-2，計算d =b^n-1 (mod n)。當d不等於1時，n是合數；當d等於1時，n則很可能是素數，對於本次判斷來説，判斷錯誤的概率為1/2。

2.如此重複多次，可以將判斷錯誤的概率降低至期望值以下。

但是，上述方法有缺陷。因為Carmichael數的存在，可導致上述算法給出一個錯誤的判斷。

前3個Carmichael數是561,1105,1729。Carmichael數是非常少的。在1~100000000範圍內的整數中，只有255個Carmichael數。 ^[1] 

列舉100000000以內的255個卡米切爾數，括號內為它的最小因子：

561(3)

1105(5)

1729(7)

2465(5)

2821(7)

6601(7)

8911(7)

10585(5)

15841(7)

29341(13)

41041(7)

46657(13)

52633(7)

62745(3)

63973(7)

75361(11)

101101(7)

115921(13)

126217(7)

162401(17)

172081(7)

188461(7)

252601(41)

2016年物流工人餘建春帶着自己的五項數學發現登上了浙江大學數學系的講台，與教授和博士生們“同堂論道”，最具價值的發現是一組“卡邁克爾數”（Carmichael數）的判別準則。

“卡邁克爾數”是一種偽素數（偽質數），在一億以內的正整數中只有255個。蔡天新驗證了餘建春提出的公式，認為在一定範圍內，餘建春的發現能夠以更高的效率找出更多的“卡邁克爾數”。

他的新算法同時得到了國際學術界的普遍讚賞。密蘇里大學數學家William Banks告訴CNN ，這種算法一經確認，即可成為卡邁克爾數領域的一大重要發現。 ^[2]