# probable prime

Fermat's little theorem gives us a powerful test for compositeness: Given*n*(greater than one), choose a positive integer

*a*and calculate

*a*

^{n-1}modulo

*n*. (There is a very easy way to evaluate this quickly by binary exponentiation.) If the result is not one modulo

*n*, then

*n*is composite. If it is one modulo

*n*, then

*n might*be prime, so

*n*is called a (weak)

**probable prime base**(or just an

*a***). (There are many other definitions for probable primes relying on other properties of primes.)**

*a*-PRPSome of these probable primes are actually composites, we call these numbers pseudoprimes. There are only 1,091,987,405 base two probable primes less than 25,000,000,000; but only 21,853 of these are pseudoprimes, so the probable prime test base two would fail only 0.0000874% of the time in this region. Henri Cohen once joked that 2-PRP's are "industrial grade primes" because they are prime often enough for many purposes.

But still, there are infinitely many composite probable primes for every base.

Below are the odd composite probable primes (pseudoprimes) less than 500 for bases 2, 3, ..., 20.

base composite weak-probable primes < 500 percentage 2 341 0.6% 3 91, 121 1.2% 4 15, 85, 91, 341, 435, 451 3.8% 5 217 0.6% 6 35, 185, 217, 301, 481 3.2% 7 25, 325 1.2% 8 9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481 8.3% 9 91, 121, 205 1.9% 10 9, 33, 91, 99, 259, 451, 481 4.4 % 11 15, 133, 259, 305, 481 3.2% 12 65, 91, 133, 143, 145, 247, 377, 385 5.1% 13 21, 85, 105, 231, 357, 427 3.8% 14 15, 39, 65, 195, 481 3.2% 15 341 0.6% 16 15, 51, 85, 91, 255, 341, 435, 451 5.1% 17 9, 45, 91, 145, 261 3.2% 18 25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451 7.0% 19 9, 15, 45, 49, 153, 169, 343 4.4% 20 21, 57, 133, 231, 399 3.2%

Note: some early articles used the name
"pseudoprimes" for what we are
calling probable primes. But now the term **pseudoprime** is usually (but not always)
properly reserved for composite probable-primes.

**See Also:** StrongPRP, CarmichaelNumber, Pseudoprime, FrobeniusPseudoprime

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

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

**References:**

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