This site will be down for maintenance beginning noon CDT (5pm UTC) Wed April 14

# 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)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].

91 = 7.13 is a 3-PRP,

217 = 7.31 is a 5-PRP and,

25 = 5.5 is a 7-PRP.

Let *t _{n}* be the least composite that
is a strong probable prime for the first

*n*primes. We now know:

Knowingt_{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}

*t*gives an efficient primality test for small numbers: all numbers less than

_{n}*t*which pass SPRP tests fore the first

_{n}*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/pseudo-prime, discovered 2*73*1103 = 161038 is an even "pseudoprime" base two.

**See Also:** CarmichaelNumber, PRP, FrobeniusPseudoprime

**Related pages** (outside of this work)

- Fermat, Probable-Primality and Pseudoprimes
- There are infinitely many pseudoprimes base
*a* - the pseudoprimes to
to 10
^{12}(by various definitions)

**References:**

- AGP94a
W. R. Alford,A. GranvilleandC. 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, Berlin, 1994. 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 10. In "Algorithmic number theory (Leiden, 2000)," Lecture Notes in Comput. Sci. Vol, 1838, Springer-Verlag, 2000. Berlin, pp. 459--473,^{13}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. SelfridgeandWagstaff, Jr., S. S., "The pseudoprimes to 25 · 10^{9},"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, 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, "FindingC_{3}-strong pseudoprimes,"Math. Comp.,74:250 (2005) 1009--1024 (electronic).MR 2114662- Zhang2007
Zhang, Zhenxiang, "Two kinds of strong pseudoprimes up to 10^{36},"Math. Comp.,76:260 (2007) 2095--2107 (electronic).MR2336285- ZT2003
Z. ZhangandM. 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)

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.