In general, an integer which has a certain property shared by all prime numbers, but is itself not prime, is called a pseudoprime for that particular property.
The most important class of pseudoprimes come from the Fermat's little theorem and hence they are called Fermat pseudoprimes. This theorem states that if p is prime and a is coprime to p, then ap-1 - 1 is divisible by p. If a number x is not prime, a is coprime to x and x divides ax-1 - 1, then x is called a pseudoprime to base a. A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number.
The smallest pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, nevertheless it satisfies Fermats little theorem; 2341=2 (mod 341).
There are applications, such as public key cryptography like RSA that need large prime numbers. The usual algorithm to generate prime numbers is to generate a random odd numbers and test them for primality. However, primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a very small chance that a composite number is declared to be prime), there are fast algorithms based on Fermat's Little Theorem. For example, a simple way to check whether a number x is prime, is to pick some random number a, and check whether x divides a x - a. If the answer is no, then x cannot be prime, if the answer is yes, x can be called a "probable prime" and the test can be repeated with other values for a. There's a separate article about the Fermat primality test.
Improved versions of this test give strong probable primes. It has been shown by Monier and Rabin that for the improved test that for each a, the chance of catching a false prime is at least 3 in 4.
There are infinitely many pseudoprimes (in fact infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudo-primes to base 2 below 1000, to a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians (SIDN A001567). Poulet numbers and Carmichael numbers (in bold) below 10000 are:
n | |
---|---|
1 | 341 = 11 · 31 |
2 | 561 = 3 · 11 · 17 |
3 | 645 = 3 · 5 · 43 |
4 | 1105 = 5 · 13 · 17 |
5 | 1387 = 19 · 73 |
6 | 1729 = 7 · 13 · 19 |
7 | 1905 = 3 · 5 · 127 |
8 | 2047 = 23 · 89 |
9 | 2465 = 5 · 17 · 29 |
10 | 2701 = 37 · 73 |
11 | 2821 = 7 · 13 · 31 |
12 | 3277 = 29 · 112 |
13 | 4033 = 37 · 109 |
14 | 4369 = 17 · 257 |
15 | 4371 = 3 · 31 · 47 |
16 | 4681 = 31 · 151 |
17 | 5461 = 43 · 127 |
18 | 6601 = 7 · 23 · 41 |
19 | 7957 = 73 · 109 |
20 | 8321 = 53 · 157 |
21 | 8481 = 3 · 11 · 257 |
22 | 8911 = 7 · 19 · 67 |
A Poulet number all of whose divisors d divide 2d - 2 is called super-Poulet number. There are an infinitely many Poulet numbers which are not super-Poulet Numbers.
The first smallest pseudoprimes for bases a ≤ 200 are given in the following table; the colors mark the number of prime factors.
a | smallest p-p | a | smallest p-p | a | smallest p-p | a | smallest p-p |
---|---|---|---|---|---|---|---|
51 | 65 = 5 ·
13 | 101 | 175 = 52 · 7 | 151 | 175 = 52 · 7 | ||
2 | 341 = 11 · 13 | 52 | 85 =
5 · 17 | 102 | 133 = 7 · 19 | 152 | 153 = 32 · 17 |
3 | 91 = 7 · 13 | 53 | 65
= 5 · 13 | 103 | 133 = 7 · 19 | 153 | 209 = 11 · 19 |
4 | 15 = 3 · 5 | 54 | 55
= 5 · 11 | 104 | 105 = 3 · 5 · 7 | 154 | 155 = 5 · 31 |
5 | 124 = 22 ·
31 | 55 | 63 = 32 · 7 | 105 | 451 = 11 · 41 | 155 | 231 = 3 · 7 · 11 |
6 | 35 = 5 · 7 | 56 | 57
= 3 · 19 | 106 | 133 = 7 · 19 | 156 | 217 = 7 · 31 |
7 | 25 | 57 | 65
= 5 · 13 | 107 | 133 = 7 · 19 | 157 | 186 = 2 · 3 · 31 |
8 | 9 | 58 | 133
= 7 · 19 | 108 | 341 = 11 · 31 | 158 | 159 = 3 · 53 |
9 | 28 = 22 ·
7 | 59 | 87 = 3 · 29 | 109 | 117 = 32 · 13 | 159 | 247 = 13 · 19 |
10 | 33 = 3 · 11 | 60 | 341
= 11 · 31 | 110 | 111 = 3 · 37 | 160 | 161 = 7 · 23 |
11 | 15 = 3 · 5 | 61 | 91
= 7 · 13 | 111 | 190 = 2 · 5 · 19 | 161 | 190=2 · 5 · 19 |
12 | 65 = 5 · 13 | 62 | 63
= 32 · 7 | 112 | 121 | 162 | 481 = 13 · 37 |
13 | 21 = 3 · 7 | 63 | 341
= 11 · 31 | 113 | 133 = 7 · 19 | 163 | 186 = 2 · 3 · 31 |
14 | 15 = 3 · 5 | 64 | 65
= 5 · 13 | 114 | 115 = 5 · 23 | 164 | 165 = 3 · 5 · 11 |
15 | 341 = 11 · 13 | 65 | 112
= 24 · 7 | 115 | 133 = 7 · 19 | 165 | 172 = 22 · 43 |
16 | 51 = 3 · 17 | 66 | 91
= 7 · 13 | 116 | 117 = 32 · 13 | 166 | 301 = 7 · 43 |
17 | 45 = 32 ·
5 | 67 | 85 = 5 · 17 | 117 | 145 = 5 · 29 | 167 | 231 = 3 · 7 · 11 |
18 | 25 | 68 | 69
= 3 · 23 | 118 | 119 = 7 · 17 | 168 | 169 |
19 | 45 = 32 ·
5 | 69 | 85 = 5 · 17 | 119 | 177 = 3 · 59 | 169 | 231 = 3 · 7 · 11 |
20 | 21 = 3 · 7 | 70 | 169 | 120 | 121 | 170 | 171
= 32 · 19 |
21 | 55 = 5 · 11 | 71 | 105
= 3 · 5 · 7 | 121 | 133 = 7 · 19 | 171 | 215 = 5 · 43 |
22 | 69 = 3 · 23 | 72 | 85
= 5 · 17 | 122 | 123 = 3 · 41 | 172 | 247 = 13 · 19 |
23 | 33 = 3 · 11 | 73 | 111
= 3 · 37 | 123 | 217 = 7 · 31 | 173 | 205 = 5 · 41 |
24 | 25 | 74 | 75
= 3 · 52 | 124 | 125 = 33 | 174 | 175 = 52 · 7 |
25 | 28 = 22 ·
7 | 75 | 91 = 7 · 13 | 125 | 133 = 7 · 19 | 175 | 319 = 11 · 19 |
26 | 27 = 33 | 76 | 77
= 7 · 11 | 126 | 247 = 13 · 19 | 176 | 177 = 3 · 59 |
27 | 65 = 5 · 13 | 77 | 247
= 13 · 19 | 127 | 153 = 32 · 17 | 177 | 196 = 22 · 72 |
28 | 45 = 32 ·
5 | 78 | 341 = 11 · 31 | 128 | 129 = 3 · 43 | 178 | 247 = 13 · 19 |
29 | 35 = 5 · 7 | 79 | 91
= 7 · 13 | 129 | 217 = 7 · 31 | 179 | 185 = 5 · 37 |
30 | 49 | 80 | 81
= 34 | 130 | 217 = 7 · 31 | 180 | 217 = 7 · 31 |
31 | 49 | 81 | 85
= 5 · 17 | 131 | 143 = 11 · 13 | 181 | 195 = 3 · 5 · 13 |
32 | 33 = 3 · 11 | 82 | 91
= 7 · 13 | 132 | 133 = 7 · 19 | 182 | 183 = 3 · 61 |
33 | 85 = 5 · 17 | 83 | 105
= 3 · 5 · 7 | 133 | 145 = 5 · 29 | 183 | 221 = 13 · 17 |
34 | 35 = 5 · 7 | 84 | 85
= 5 · 17 | 134 | 135 = 33 · 5 | 184 | 185 = 5 · 37 |
35 | 51 = 3 · 17 | 85 | 129
= 3 · 43 | 135 | 221 = 13 · 17 | 185 | 217 = 7 · 31 |
36 | 91 = 7 · 13 | 86 | 87
= 3 · 29 | 136 | 265 = 5 · 53 | 186 | 187 = 11 · 17 |
37 | 45 = 32 ·
5 | 87 | 91 = 7 · 13 | 137 | 148 = 22 · 37 | 187 | 217 = 7 · 31 |
38 | 39 = 3 · 13 | 88 | 91
= 7 · 13 | 138 | 259 = 7 · 37 | 188 | 189 = 33 · 7 |
39 | 95 = 5 · 19 | 89 | 99
= 32 · 11 | 139 | 161 = 7 · 23 | 189 | 235 = 5 · 47 |
40 | 91 = 7 · 13 | 90 | 91
= 7 · 13 | 140 | 141 = 3 · 47 | 190 | 231 = 3 · 7 · 11 |
41 | 105 = 3 · 5 ·
7 | 91 | 115 = 5 · 23 | 141 | 355 = 5 · 71 | 191 | 217 = 7 · 31 |
42 | 205 = 5 · 41 | 92 | 93
= 3 · 31 | 142 | 143 = 11 · 13 | 192 | 217 = 7 · 31 |
43 | 77 = 7 · 11 | 93 | 301
= 7 · 43 | 143 | 213 = 3 · 71 | 193 | 276 = 22 · 3 · 23 |
44 | 45 = 32 ·
5 | 94 | 95 = 5 · 19 | 144 | 145 = 5 · 29 | 194 | 195 = 3 · 5 · 13 |
45 | 76 = 22 ·
19 | 95 | 141 = 3 · 47 | 145 | 153 = 32 · 17 | 195 | 259 = 7 · 37 |
46 | 133 = 7 · 19 | 96 | 133
= 7 · 19 | 146 | 147 = 3 · 72 | 196 | 205 = 5 · 41 |
47 | 65 = 5 · 13 | 97 | 105
= 3 · 5 · 7 | 147 | 169 | 197 | 231 = 3 · 7 · 11 |
48 | 49 | 98 | 99
= 32 · 11 | 148 | 231 = 3 · 7 · 11 | 198 | 247 = 13 · 19 |
49 | 66 = 2 · 3 ·
11 | 99 | 145 = 5 · 29 | 149 | 175 = 52 · 7 | 199 | 225 = 32 · 52 |
50 | 51 = 3 · 17 | 100 | 153
= 32 · 17 | 150 | 169 | 200 | 201 = 3 · 67 |
See also: