伪素数，又叫做伪质数:它满足费马小定理，但其本身却不是素数。最小的伪素数是341。有人已经证明了伪素数的个数是无穷的。事实上，费马小定理给出的是关于素数判定的必要非充分条件。若n能整除2^(n-1)-1，并n是非偶数的合数，那么n就是伪素数。第一个伪素数341 是萨鲁斯(Sarrus)在1819年发现的。1903年，马洛(Malo)证明:若n为伪素数，则<math>m=2^n-1</math>也是一个伪素数，从而肯定了伪素数的个数是无穷的。1950年，发现第一个偶伪素数161038=2*73*1103。