伪素数是指满足素数的某种性质，但并非素数的数。最有名的伪素数是满足费马小定理的合数。严格的定义是：对自然数和一个与其互素的自然数a，如果整除 a - 1，则称是一个以a为底的伪素数或者关于a的伪素数。最小的伪素数是341（=11×31，关于2）。如果关于任何与其互素的数都是伪素数，则称是绝对伪素数（或卡迈克尔数，来自找到第一个绝对伪素数的数学家罗伯特·丹尼·卡迈克尔）。最小的绝对伪素数是561。

有人已经证明了伪素数的个数是无穷的。有一位数学家如此评论：“对于素数，费马小定理肯定是正确的；但他没说在合数中就不正确。”事实上，费马小定理给出的是关于素数判定的必要非充分条件。

A pseudoprime is a probable prime (an integer that shares a property common to all prime numbers) that is not actually prime. Pseudoprimes are classified according to which property of primes they satisfy.

Some sources use the term pseudoprime about all probable primes, both composite numbers and actual primes.