Glossary:
Prime Pages:
Top 5000:

A probableprime which is composite is called a
pseudoprime. (At one time all probable primes
were called pseudoprimes, but now the terminology has
been corrected.) The smallest examples of
pseudoprimes for bases 2, 3, 5, and 7 are as follows.
341 = 11.31 is a 2PRP, (Sarrus 1819)
91 = 7.13 is a 3PRP,
217 = 7.31 is a 5PRP and,
25 = 5.5 is a 7PRP.
It is harder to find examples of composites which are
probable primes (or better, strong probable
primes) to several bases, but this is always
possible [AGP94a].
Let t_{n} be the least composite that
is a strong probable prime for the first n
primes. We now know:
t_{1} = 23 ^{.} 89
t_{2} = 829 ^{.} 1657
t_{3} = 2251 ^{.} 11251
t_{4} = 151 ^{.} 751 ^{.} 28351
t_{5} =
6763 ^{.} 10627 ^{.} 29947
t_{6} =
1303 ^{.} 16927 ^{.} 157543
t_{7} = 10670053 ^{.} 32010157
t_{8} = 10670053 ^{.} 32010157
t_{9}
< 149491 ^{.} 747451 ^{.} 34233211
t_{10}
< 149491 ^{.} 747451 ^{.} 34233211
t_{11}
< 149491 ^{.} 747451 ^{.} 34233211
t_{12} <
399165290221 ^{.} 798330580441
t_{13} < 1287836182261 ^{.} 2575672364521
t_{14} < 54786377365501 ^{.} 109572754731001
t_{15} < 172157429516701 ^{.} 344314859033401
t_{16} < 531099297693901 ^{.} 1062198595387801
t_{17} < 531099297693901 ^{.} 1062198595387801
t_{18} < 27778299663977101 ^{.} 55556599327954201
t_{19} < 27778299663977101 ^{.} 55556599327954201
t_{20} > 10^{36}
Knowing t_{n} gives an efficient primality
test for small numbers: all numbers less than t_{n}
which pass SPRP tests fore the first n primes are indeed
prime!
Arnault found a 337 digit number which passed strong PRP tests for each of the 46 primes below 200 [Arnault95].
It is interesting to note that in 1950 Lehmer, using the weaker
definition a^{n} = a (mod n) for
probable/pseudoprime, discovered 2*73*1103 = 161038 is an even
"pseudoprime" base two.
See Also: CarmichaelNumber, PRP, FrobeniusPseudoprime Related pages (outside of this work) References:
 AGP94a
 W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses. In "Algorithmic Number Theory, First International Symposium, ANTSI," L. M. Adleman and M. D. Huang editors, Lecture Notes in Computer Science Vol, 877, SpringerVerlag, 1994. Berlin, pp. 116, MR 96d:11136
 Arnault95
 F. Arnault, "RabinMiller primality test: composite numbers which pass it," Math. Comp., 64:209 (1995) 355361. MR 95c:11152
 Jaeschke93
 G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915926. MR 94d:11004
 Pinch2000
 R. Pinch, The pseudoprimes up to 10^{13}. In "Algorithmic number theory (Leiden, 2000)," Lecture Notes in Comput. Sci. Vol, 1838, SpringerVerlag, 2000. Berlin, pp. 459473, MR 2002g:11177
 Pomerance84
 C. Pomerance, Lecture notes on primality testing and factoring (notes by G. M. Gagola Jr.), Notes Vol, 4, Mathematical Association of America, 1984. pp. 34 pages,
 PSW80
 C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10^{9}," Math. Comp., 35:151 (1980) 10031026. MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
 Ribenboim95
 P. Ribenboim, The new book of prime number records, 3rd edition, SpringerVerlag, New York, NY, 1995. pp. xxiv+541, ISBN 0387944575. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventyfive pages.]
 Zhang2000
 Z. Zhang, "Finding strong pseudoprimes to several bases," Math. Comp., 70:234 (2001) 863872. MR 2001g:11009 (Abstract available)
 Zhang2005a
 Z. Zhang, "Finding C_{3}strong pseudoprimes," Math. Comp., 74:250 (2005) 10091024 (electronic). MR 2114662
 Zhang2007
 Zhang, Zhenxiang, "Two kinds of strong pseudoprimes up to 10^{36}," Math. Comp., 76:260 (2007) 20952107 (electronic). MR2336285
 ZT2003
 Z. Zhang and M. Tang, "Finding strong pseudoprimes to several bases. II," Math. Comp., 72:244 (2003) 20852097 (electronic). http://www.ams.org/journalgetitem?pii=S002557180301545X. MR 2004c:11008 (Abstract available)
