偽素數是指很像素數,但並不一定是素數的數。根據所滿足的性質的不同可以劃分不同種類的偽素數。其中最有名的偽素數是滿足費馬小定理的合數,即費馬偽素數。
費馬偽素數的定義是:對自然數 x {\displaystyle x} 和一個與其互素的自然數a,如果 x {\displaystyle x} 整除 ax-1 - 1,則稱 x {\displaystyle x} 是一個以a為底的費馬偽素數或者關於a的費馬偽素數。最小的費馬偽素數是341(=11×31,關於2)。如果 x {\displaystyle x} 關於任何與其互素的數都是費馬偽素數,則稱 x {\displaystyle x} 是絕對偽素數(或卡邁克爾數),來自找到第一個絕對偽素數的數學家羅伯特·丹尼·卡邁克爾)。最小的絕對偽素數是561。