費馬小定理說明所有質(zhì)數(shù)都有這個性質(zhì)。在這方面，卡邁克爾數(shù)和質(zhì)數(shù)十分相似，所以它們稱為偽素數(shù)。
卡邁克爾數(shù)的定義是對于合數(shù)n，如果對于所有與n互質(zhì)的正整數(shù)b，都有同余式b^(n-1)≡1(modn)成立，則稱合數(shù)n為Carmichael數(shù)。
2016年物流工人余建春帶著自己的五項數(shù)學發(fā)現(xiàn)登上了浙江大學數(shù)學系的講臺，與教授和博士生們“同堂論道”，最具價值的發(fā)現(xiàn)是一組“卡邁克爾數(shù)”（Carmichael數(shù)）的判別準則。
定理介紹
1.每個Carmichael至少是三個不同素數(shù)的乘積。如。
費馬小定理(Fermat theorem)：
設(shè)p為一素數(shù)，對于任意整數(shù)a，有。
假如p是質(zhì)數(shù)，且，那么 假如p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的次方除以p的余數(shù)恒等于1
性質(zhì)
卡邁克爾數(shù)有至少3個正素因數(shù)。如圖一是首個k個正素因數(shù)的卡邁克爾數(shù)，
費馬判定
設(shè)p為一素數(shù)，而a與p互素，則必為p的倍數(shù)。 利用費馬小定理，對于給定的整數(shù)n，可以設(shè)計一個素數(shù)判定算法。通過計算來判定整數(shù)n的素性。當d不等于1時，n肯定不是素數(shù)；當d等于1時，n則很可能是素數(shù)。但也存在合數(shù)n使得。例如，當時，滿足的最小合數(shù)是。為了提高測試的準確性，我們可以隨機地選取多個a對n的結(jié)果進行測試。能通過全部a的測試的合數(shù)n，被稱為Carmichael數(shù)，前3個Carmichael數(shù)是561,1105,1729。Carmichael數(shù)是非常少的。在1~100000000范圍內(nèi)的整數(shù)中，只有255個Carmichael數(shù)。
素性檢驗
由費馬小定理可得，若n為素數(shù)，則對任意整數(shù)b，且b和n互素，都有。因此，若存在整數(shù)b，使得不成立，則n是一個合數(shù)。
利用上述結(jié)論，對于給定的整數(shù)n，可以設(shè)計一個素數(shù)判定算法。
1.隨機選取整數(shù)b，，計算。當d不等于1時，n是合數(shù)；當d等于1時，n則很可能是素數(shù)，對于本次判斷來說，判斷錯誤的概率為。
2.如此重復多次，可以將判斷錯誤的概率降低至期望值以下。
但是，上述方法有缺陷。因為Carmichael數(shù)的存在，可導致上述算法給出一個錯誤的判斷。
前3個Carmichael數(shù)是561,1105,1729。Carmichael數(shù)是非常少的。在1~100000000范圍內(nèi)的整數(shù)中，只有255個Carmichael數(shù)。?
列舉數(shù)組
列舉100000000以內(nèi)的255個卡米切爾數(shù)，括號內(nèi)為它的最小因子：
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年物流工人余建春帶著自己的五項數(shù)學發(fā)現(xiàn)登上了浙江大學數(shù)學系的講臺，與教授和博士生們“同堂論道”，最具價值的發(fā)現(xiàn)是一組“卡邁克爾數(shù)”（Carmichael數(shù)）的判別準則。
“卡邁克爾數(shù)”是一種偽素數(shù)（偽質(zhì)數(shù)），在一億以內(nèi)的正整數(shù)中只有255個。蔡天新驗證了余建春提出的公式，認為在一定范圍內(nèi)，余建春的發(fā)現(xiàn)能夠以更高的效率找出更多的“卡邁克爾數(shù)”。
他的新算法同時得到了國際學術(shù)界的普遍贊賞。密蘇里大學數(shù)學家William Banks告訴CNN ，這種算法一經(jīng)確認，即可成為卡邁克爾數(shù)領(lǐng)域的一大重要發(fā)現(xiàn)。
參考資料 >