pseudoprime (another Prime Pages' Glossary entries)
 Glossary: Prime Pages: Top 5000: A probable-prime 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 2-PRP, (Sarrus 1819) 91 = 7.13 is a 3-PRP, 217 = 7.31 is a 5-PRP and, 25 = 5.5 is a 7-PRP. 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 tn be the least composite that is a strong probable prime for the first n primes. We now know: t1 = 23 . 89 t2 = 829 . 1657 t3 = 2251 . 11251 t4 = 151 . 751 . 28351 t5 = 6763 . 10627 . 29947 t6 = 1303 . 16927 . 157543 t7 = 10670053 . 32010157 t8 = 10670053 . 32010157 t9 < 149491 . 747451 . 34233211 t10 < 149491 . 747451 . 34233211 t11 < 149491 . 747451 . 34233211 t12 < 399165290221 . 798330580441 t13 < 1287836182261 . 2575672364521 t14 < 54786377365501 . 109572754731001 t15 < 172157429516701 . 344314859033401 t16 < 531099297693901 . 1062198595387801 t17 < 531099297693901 . 1062198595387801 t18 < 27778299663977101 . 55556599327954201 t19 < 27778299663977101 . 55556599327954201 t20 > 1036 Knowing tn gives an efficient primality test for small numbers: all numbers less than tn 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 an = a (mod n) for probable/pseudo-prime, discovered 2*73*1103 = 161038 is an even "pseudoprime" base two. See Also: CarmichaelNumber, PRP, FrobeniusPseudoprimeRelated 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, ANTS-I," L. M. Adleman and M. D. Huang editors, Lecture Notes in Computer Science Vol, 877, Springer-Verlag, 1994.  Berlin, pp. 1--16, MR 96d:11136 Arnault95 F. Arnault, "Rabin-Miller primality test: composite numbers which pass it," Math. Comp., 64:209 (1995) 355--361.  MR 95c:11152 Jaeschke93 G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926.  MR 94d:11004 Pinch2000 R. Pinch, The pseudoprimes up to 1013.  In "Algorithmic number theory (Leiden, 2000)," Lecture Notes in Comput. Sci. Vol, 1838, Springer-Verlag, 2000.  Berlin, pp. 459--473, 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 · 109," Math. Comp., 35:151 (1980) 1003-1026.  MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].] Ribenboim95 P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, 1995.  New York, NY, pp. xxiv+541, ISBN 0-387-94457-5. 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 seventy-five pages.] Zhang2000 Z. Zhang, "Finding strong pseudoprimes to several bases," Math. Comp., 70:234 (2001) 863--872.  MR 2001g:11009 (Abstract available) Zhang2005a Z. Zhang, "Finding C3-strong pseudoprimes," Math. Comp., 74:250 (2005) 1009--1024 (electronic).  MR 2114662 Zhang2007 Zhang, Zhenxiang, "Two kinds of strong pseudoprimes up to 1036," Math. Comp., 76:260 (2007) 2095--2107 (electronic).  MR2336285 ZT2003 Z. Zhang and M. Tang, "Finding strong pseudoprimes to several bases. II," Math. Comp., 72:244 (2003) 2085--2097 (electronic).  http://www.ams.org/journal-getitem?pii=S0025-5718-03-01545-X.  MR 2004c:11008 (Abstract available) Chris K. Caldwell © 1999-2018 (all rights reserved)