Un número compuesto $m$ se dice pseudoprimo si $m$ divide a $2^m - 2$. En términos de congruencias, esto se escribe así: $$2^m \equiv 2 \pmod{m}$$
Esta definición está inspirada en el Pequeño teorema de Fermat, que dice que para todo primo $p$ se tiene que $a^p \equiv a \pmod{p}$, y en el caso particular de $a=2$ es cierto que $2^p \equiv 2\pmod{p}$ para todo primo $p$. En este sentido, son pseudoprimos, pues satisfacen una propiedad que todos los primos satisfacen pero no son primos.
Los pseudoprimos más pequeños que se conocen son 341, 561, 645 y 1105.
Es posible demostrar que hay una infinidad de pseudoprimos.