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 a (or just an a-PRP). (There are many other definitions for probable primes relying on other properties of primes.)

Some 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%

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.

Related pages (outside of this work)

References:

PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10⁹," 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.]