1640年 6月，法國數學大師費馬 (Pierre de Fermat 1601-1665) 在給梅森 (Marin Mersenne 1588-1648) 的信中提及若干事實，詳見《梅森素數》一文，其中：

若 p 為素數，則 2^p - 2 能被 p 整除。這相當於 2^p-1-1 能被 p 整除。

後來在 1640年 10月 18日，他給貝西 (Frenicle de Bessy 1605-1675) 的一封信中更指出他證明了：

若 p 為素數， a 與 p 互素，則 a^p-1-1 能被 p 整除。

以同餘式 (Congruence Expression) 表示則是，

a^p-1 = 1 (mod p)

這便是著名的費馬小定理 (Fermat's Little Theorem 或 Fermat's Lesser Theorem) ，或費馬同餘式 (Fermat's Congruence Expression)。被冠以「小」的名字只是為了和世紀難題費馬大定理 (Fermat's Last Theorem) 相分，不存在任何貶意。為了方便對費馬小定理作研究，數學家定義了費馬商 (Fermat Quotient)：

若 p 不整除 a 或 b ，我們有

q_p(ab) = q_p(a) + q_p(b)

q_p(p+1) = -1；q_p(p-1) = 1

　

據此，如果 n 與 a 互素，且不能整除 a^n-1- 1， 則 n 必不是素數，即是合數。但如果 n 能整除 a^n-1-1 又怎樣？ n 是素數嗎？即是問費馬小定理的逆命題 (Converse of Fermat's Little Theorem) 是成立嗎？

西方很長的時間以為這費馬小定理的逆命題是成立的，對於 1 < n < 300 的驗證中，能整除 2^n-1-1 的奇數 n 全是素數，即大大支持了成立逆命題。附帶一言，以 a = 2 的費馬小定理逆命題，亦被稱為中國假設 (Chinese Hypothesis)，但這似乎是西方人對中國古代數學的過分推崇而已，此命題和中國似乎連不上任何關係。普魯士數學家哥德巴赫 (Christian Goldbach 1690-1764) 在其寄給歐拉 (Leonhard Euler 1707-1783) 的信中還表示他會嘗試證明這逆命題。結果如何，他自然是失敗而回。在 1819年，法國數學家賽路斯 (Sarrus) 找到了一反例  (Counterexample) 是 341 ，341雖可整除 2³⁴⁰ - 1 ，但 341 = 11*31 是一合數。這一刻數學家才知道費馬小定理的逆命題是不成立的。事實上，在沒有計算機等電子工具之助的年代，要對費馬小定理的逆命題作測試是一件極不容易之事。除了 341 以外，人們還找到了 561 、 645 、 1105 、 1387 、 1729 、 1905 等 (OEIS A001567) 。他們全是合數也符合費馬小定理的要求，我們稱這些合數為費馬偽素數 (Fermat Pseudoprime) ，簡稱偽素數 (Pseudoprime) 。

　

以 a 為底的偽素數

若 n 為合數，且能整除 a^n-1-1，我們稱 n 為以 a 為底的偽素數 (Pseudoprime to Base a, 或 psp(a) )，這是把以往的偽素數觀念作了推廣。當然最先為數學家研究的會是以 2 為底的偽素數 (Pseudoprime to Base 2, 或 psp(2)，如此類推，下同) ，這亦被稱作賽路斯數 (Sarrus Number) 或包列迪數 (Poulet Number) ，因為包列迪 (P. Poulet) 對這個問題花了不少精力。特別地，他在 1926年 計算了五千萬以內的偽素數，又於 1938年 計算到 10⁸。我們已得知以某數為底的偽素數是有無限個之多。這無疑是對素數判定澆了一盤冷水。

　

下表列出一些以 2 或以 3 為底的偽素數：

底數 n	偽素數	斯洛恩數列
2	341、561、645、1105、1387、1729、1905、2047、2465、2701、2821、3277、4033、4369、4371、4681、...	A001567
3	91、121、286、671、703、949、1105、1541、1729、1891、2465、2665、2701、2821、3281、3367、3751、4961、...	A005935
2 & 3	1105、1729、2465、2701、2821、...	A052155

小小題外話，別以為以 2 為底的偽素數全是奇數，其實也有偶數，如 161038 或 215326 等 (OEIS A006935)。

　

有些數學家提出了一些構造 以 a 為底的偽素數的方法。

其中，1904年，薛波拉 (M. Cipolla) 給出了以下的方法：

設 a 不小於 2 ， p 為奇素數且不能整除 a(a² - 1) 。

令 n₁= (a^p- 1) / (a - 1) 及 n₂= (a^p+ 1) / (a + 1) ，n = n₁* n₂

則 n₁ 和 n₂ 均為奇數，而 n 是合成數亦同為 以 a 為底的偽素數了。

其後還有很多數學家提出不同的方法，本文不作冗述了。

　

下表為對於一些底的最小偽素數。

底	最小偽素數
2	341 = 11 * 31
3	91 = 7 * 13
5	217 = 7 * 31
7	25 = 5 * 5
2, 3	1105 = 5 * 13 * 17
2, 5	561 = 3 * 11 *17
2, 7	561 = 3 * 11 *17
3, 5	1541 = 23 * 67
3, 7	703 = 19 * 73
5, 7	561 = 3 * 11 * 17
2, 3, 5	1729 = 7 * 13 * 19
2, 3, 7	1105 = 5 * 13 * 17
2, 5, 7	561 = 3 * 11 * 17
3, 5, 7	29341 = 13 * 37 * 61
2, 3, 5, 7	29341 = 13 * 37 * 61

 

卡邁克爾數

在尋找偽素數的同時，數學家也對偽素數的個數進行了分析：

在 首 10億個自然數中，有 50847534 個素數，而以 2 為底的偽素數則只有 5597個。因此在整除 2^n-1-1 的情況下，出現合數的機會僅有 5597/(5597+50847534) = 0.00011 ，即約 萬分之一。

而我們同時考慮以 2 和 3 為底的偽素數，則只有 1272 個。因此同時以整除 2^n-1-1 和整除 3^n-1-1 的情況下，碰上合數的機會便更低了，僅有 1272/(1272+50847534) = 0.000025。

於是以費馬小定理作素數判定仍有一定大的機會可信 ， 符合費馬小定理逆命題的數 ， 我們稱為擬素數 (Probable Prime) 。這擬素數一是素數，二是偽素數。人們自然會想，若我們把這測試擴張至其他式底，自然會把找到偽素數的機會降低，會降至 0 嗎？

　

答案是令人失望的不會。在 1912年美國數學家卡邁克爾 (Robert Daniel Carmichael 1879-1967) 發現數 561 能整除所有 a⁵⁶⁰-1 ，而 a 與 561 互素，但 561 = 3*11*17 是一合數。我們稱這樣的數為卡邁克爾數 (Carmichael Number)。卡邁克爾不單發現了這數的存在，還找到了一判定法則，這我們稱為卡邁克爾條件 (Carmichael Condition)：

n 不能被一完全平方數整除。

n 是奇數，且至少含有三個不同的素因子。

對於 n 的每一個素因子 p ，n-1 能被 p-1 整除。

若 n 符合上述三條件，則 n 是卡邁克爾數，反之，若 n 是卡邁克爾數，n 亦會符合該三條件。

以我們先前談及的 561看看，這顯然滿足了首兩個條件。另一方面 561 = 3*11*17，而 561-1 = 560 = 2⁴*5*7 ，3-1=2 、 11-1 = 10 = 2*5、17-1 = 16 = 2⁴全是 560 的因子。