  We introduce a new class of pseudoprimes-so called "overpseudoprimes to base
$b$", which is a subclass of strong pseudoprimes to base $b$. Denoting via
$|b|_n$ the multiplicative order of $b$ modulo $n$, we show that a composite
$n$ is overpseudoprime if and only if $|b|_d$ is invariant for all divisors
$d>1$ of $n$. In particular, we prove that all composite Mersenne numbers
$2^{p}-1$, where $p$ is prime, are overpseudoprime to base 2 and squares of
Wieferich primes are overpseudoprimes to base 2. Finally, we show that some
kinds of well known numbers are overpseudoprime to a base $b$.
