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.

Title	pseudoprime
Canonical name	Pseudoprime
Date of creation	2013-03-22 16:49:44
Last modified on	2013-03-22 16:49:44
Owner	CompositeFan (12809)
Last modified by	CompositeFan (12809)
Numerical id	6
Author	CompositeFan (12809)
Entry type	Definition
Classification	msc 11A51