# pseudoprime

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.

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, 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, Berlin, 2000.  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
Ribenboim95
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995.  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-XMR 2004c:11008 (Abstract available)