use the term strong pseudoprime.) The definition is trivially met if so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes. Properties of strong pseudoprimes A strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, an Euler pseudoprime and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Carmichael numbers may be strong pseudoprimes to some bases—for example, 561 is a strong pseudoprime to base 50—but not to all bases. A composite number n is a strong pseudoprime to at most one quarter of all bases below n; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases. Thus given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, forming the basis of the widely used Miller–Rabin primality test. The true probability of a failure is generally vastly smaller. Paul Erdos and Carl Pomerance showed in 1986 that if a random integer n passes the Miller–Rabin primality test to a random base b, then n is almost surely a prime. For example, of the first 25,000,000,000 positive integers, there are 1,091,987,405 integers that are probable primes to base 2, but only 21,853 of them are pseudoprimes, and even fewer of them are strong pseudoprimes, as the latter is a subset of the former. However, Arnault gives a 397-digit Carmichael number that is a strong pseudoprime to every base less than 307. One way to reduce the chance that such a number is wrongfully declared probably prime is to combine a strong probable prime test with a Lucas probable prime test, as in the Baillie–PSW primality test. There are infinitely many strong pseudoprimes to any base. Examples The first strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... . The first to base 3 are 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... . The first to base 5 are 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... . For base 4, see , and for base 6 to 100, see to . By testing