Fermat's little theorem gives us a powerful test for
compositeness: Given n (greater than one), choose
a positive integer a and calculate an-1 modulo n. (There is
a very easy way to evaluate this quickly by binary exponentiation.) If
the result is not one modulo n, then n is
composite. If it is one modulo n, then n
might be prime, so n is called a (weak) probable prime
base a (or just an a-PRP).
(There are many other definitions for probable primes
relying on other properties of primes.)
Some of these probable primes are actually composites, we call these numbers pseudoprimes. There are only 1,091,987,405 base two probable primes less than 25,000,000,000; but only 21,853 of these are pseudoprimes, so the probable prime test base two would fail only 0.0000874% of the time in this region. Henri Cohen once joked that 2-PRP's are "industrial grade primes" because they are prime often enough for many purposes.
But still, there are infinitely many composite probable primes for every base.
Below are the odd composite probable primes (pseudoprimes) less than 500 for bases 2, 3, ..., 20.
Note: some early articles used the name "pseudoprimes" for what we are calling probable primes. But now the term pseudoprime is usually (but not always) properly reserved for composite probable-primes.
Related pages (outside of this work)