pseudoprime

A pseudoprime is a composite number $p$ that passes a given primality test. In other words, a pseudoprime is a false positive on a primality test.

The primality test is usually a power congruence to a given base $b$ that is coprime to $p$, such as $b^{p-1}\equiv 1modp$ (from Fermat’s little theorem). For example, if $p$ is an odd prime, then the congruence $2^{p-1}\equiv 1modp$ will be true, but in reverse, $p$ can satisfy the congruence but turn out to be an odd composite number. Such pseudoprimes are then called pseudoprime to base $b$, and in our example with $b=2$, the first few are 341, 561, 645, 1105, 1387, 1729, 1905 (A001567 in Sloane’s OEIS). According to Neil Sloane, writing in the OEIS, the term “pseudoprime” is sometimes used specifically to refer to pseudoprimes to base 2. These are sometimes called Sarrus numbers.

Another kind of pseudoprimes are those in which a composite $p$ divides an element it indexes in a Fibonacci-like sequence. For example, a Perrin pseudoprime $p$ divides $a_p$, where $a_n$ is the $n$-th element in the Perrin sequence.