In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For a positive integer a, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a.[1] In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.[2] The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the Chinese hypothesis.
The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes theFermat primality test for the base 2.
Pseudoprimes to base 2 are sometimes called Sarrus numbers, after P. F. Sarrus who discovered that 341 has this property, Poulet numbers, after P. Poulet who made a table of such numbers, or Fermatians .
A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.
An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.
There are infinitely many pseudoprimes to any given base a > 1. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base a > 1: let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1), where p is a prime number that does not divide a(a2 - 1). Then n = AB is composite, and is a pseudoprime to base a.[3] [4] For example, if a = 2 and p = 5, then A = 31, B = 11, and n = 341 is a pseudoprime to base 2.
In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of[5]) and infinitely many Carmichael numbers,[6] but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·109. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of [5]).
Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all Fermat composites and Mersenne composites.
The probability of a composite number n passing the Fermat test approaches zero for
n\toinfty
1<b<n-1
The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table.
|
|
|
|
A Poulet number all of whose divisors d divide 2d − 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers.
The smallest pseudoprime for each base a ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below a are excluded in the table. (For that to allow pseudoprimes below a, see)
| a | smallest p-p | a | smallest p-p | a | smallest p-p | a | smallest p-p | |
|---|---|---|---|---|---|---|---|---|
| 1 | 4 = 2² | 51 | 65 = 5 · 13 | 101 | 175 = 5² · 7 | 151 | 175 = 5² · 7 | |
| 2 | 341 = 11 · 31 | 52 | 85 = 5 · 17 | 102 | 133 = 7 · 19 | 152 | 153 = 3² · 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 = 2² · 31 | 55 | 63 = 3² · 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 = 5² | 57 | 65 = 5 · 13 | 107 | 133 = 7 · 19 | 157 | 186 = 2 · 3 · 31 | |
| 8 | 9 = 3² | 58 | 133 = 7 · 19 | 108 | 341 = 11 · 31 | 158 | 159 = 3 · 53 | |
| 9 | 28 = 2² · 7 | 59 | 87 = 3 · 29 | 109 | 117 = 3² · 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 = 3² · 7 | 112 | 121 = 11² | 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 · 31 | 65 | 112 = 2⁴ · 7 | 115 | 133 = 7 · 19 | 165 | 172 = 2² · 43 | |
| 16 | 51 = 3 · 17 | 66 | 91 = 7 · 13 | 116 | 117 = 3² · 13 | 166 | 301 = 7 · 43 | |
| 17 | 45 = 3² · 5 | 67 | 85 = 5 · 17 | 117 | 145 = 5 · 29 | 167 | 231 = 3 · 7 · 11 | |
| 18 | 25 = 5² | 68 | 69 = 3 · 23 | 118 | 119 = 7 · 17 | 168 | 169 = 13² | |
| 19 | 45 = 3² · 5 | 69 | 85 = 5 · 17 | 119 | 177 = 3 · 59 | 169 | 231 = 3 · 7 · 11 | |
| 20 | 21 = 3 · 7 | 70 | 169 = 13² | 120 | 121 = 11² | 170 | 171 = 3² · 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 = 5² | 74 | 75 = 3 · 5² | 124 | 125 = 5³ | 174 | 175 = 5² · 7 | |
| 25 | 28 = 2² · 7 | 75 | 91 = 7 · 13 | 125 | 133 = 7 · 19 | 175 | 319 = 11 · 19 | |
| 26 | 27 = 3³ | 76 | 77 = 7 · 11 | 126 | 247 = 13 · 19 | 176 | 177 = 3 · 59 | |
| 27 | 65 = 5 · 13 | 77 | 247 = 13 · 19 | 127 | 153 = 3² · 17 | 177 | 196 = 2² · 7² | |
| 28 | 45 = 3² · 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 = 7² | 80 | 81 = 3⁴ | 130 | 217 = 7 · 31 | 180 | 217 = 7 · 31 | |
| 31 | 49 = 7² | 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 = 3³ · 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 = 3² · 5 | 87 | 91 = 7 · 13 | 137 | 148 = 2² · 37 | 187 | 217 = 7 · 31 | |
| 38 | 39 = 3 · 13 | 88 | 91 = 7 · 13 | 138 | 259 = 7 · 37 | 188 | 189 = 3³ · 7 | |
| 39 | 95 = 5 · 19 | 89 | 99 = 3² · 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 = 2² · 3 · 23 | |
| 44 | 45 = 3² · 5 | 94 | 95 = 5 · 19 | 144 | 145 = 5 · 29 | 194 | 195 = 3 · 5 · 13 | |
| 45 | 76 = 2² · 19 | 95 | 141 = 3 · 47 | 145 | 153 = 3² · 17 | 195 | 259 = 7 · 37 | |
| 46 | 133 = 7 · 19 | 96 | 133 = 7 · 19 | 146 | 147 = 3 · 7² | 196 | 205 = 5 · 41 | |
| 47 | 65 = 5 · 13 | 97 | 105 = 3 · 5 · 7 | 147 | 169 = 13² | 197 | 231 = 3 · 7 · 11 | |
| 48 | 49 = 7² | 98 | 99 = 3² · 11 | 148 | 231 = 3 · 7 · 11 | 198 | 247 = 13 · 19 | |
| 49 | 66 = 2 · 3 · 11 | 99 | 145 = 5 · 29 | 149 | 175 = 5² · 7 | 199 | 225 = 3² · 5² | |
| 50 | 51 = 3 · 17 | 100 | 153 = 3² · 17 | 150 | 169 = 13² | 200 | 201 = 3 · 67 |
| n | First few Fermat pseudoprimes in base n | OEIS sequence | |
| 1 | 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, ... (All composites) | ||
| 2 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... | ||
| 3 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... | ||
| 4 | 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ... | ||
| 5 | 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... | ||
| 6 | 35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ... | ||
| 7 | 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... | ||
| 8 | 9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, ... | ||
| 9 | 4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, ... | ||
| 10 | 9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, ... | ||
| 11 | 10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, ... | ||
| 12 | 65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073, ... | ||
| 13 | 4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637, ... | ||
| 14 | 15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073, ... | ||
| 15 | 14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... | ||
| 16 | 15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919, ... | ||
| 17 | 4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, ... | ||
| 18 | 25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061, ... | ||
| 19 | 6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997, ... | ||
| 20 | 21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911, ... | ||
| 21 | 4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, ... | ||
| 22 | 21, 69, 91, 105, 161, 169, 345, 483, 485, 645, 805, 1105, 1183, 1247, 1261, 1541, 1649, 1729, 1891, 2037, 2041, 2047, 2413, 2465, 2737, 2821, 3241, 3605, 3801, 5551, 5565, 5963, 6019, 6601, 6693, 7081, 7107, 7267, 7665, 8119, 8365, 8421, 8911, 9453, ... | ||
| 23 | 22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027, 1045, 1065, 1105, 1183, 1271, 1729, 1738, 1749, 2059, 2321, 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651, 8745, 8911, 8965, 9805, ... | ||
| 24 | 25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2701, 2737, 2821, 2885, 3781, 4207, 4537, 6601, 6931, 6943, 7081, 7189, 7471, 7501, 7813, 8725, 8911, 9085, 9361, 9809, ... | ||
| 25 | 4, 6, 8, 12, 24, 28, 39, 66, 91, 124, 217, 232, 276, 403, 426, 451, 532, 561, 616, 703, 781, 804, 868, 946, 1128, 1288, 1541, 1729, 1891, 2047, 2701, 2806, 2821, 2911, 2926, 3052, 3126, 3367, 3592, 3976, 4069, 4123, 4207, 4564, 4636, 4686, 5321, 5461, 5551, 5611, 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9976, ... | ||
| 26 | 9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 925, 1035, 1065, 1147, 2465, 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 8029, 8695, 8911, 9073, ... | ||
| 27 | 26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1729, 1891, 2071, 2465, 2665, 2701, 2821, 2981, 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8911, 9139, 9709, 9809, 9841, 9881, 9919, ... | ||
| 28 | 9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1305, 1413, 1431, 1885, 2041, 2413, 2465, 2871, 3201, 3277, 4553, 4699, 5149, 5181, 5365, 7065, 8149, 8321, 8401, 9841, ... | ||
| 29 | 4, 14, 15, 21, 28, 35, 52, 91, 105, 231, 268, 341, 364, 469, 481, 561, 651, 793, 871, 1105, 1729, 1876, 1897, 2105, 2257, 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7294, 8321, 8401, 8421, 8841, 8911, ... | ||
| 30 | 49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 3283, 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8401, 8911, 9881, ... |
For more information (base 31 to 100), see to, and for all bases up to 150, see table of Fermat pseudoprimes (text in German), this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n)
If composite
n
n
b\equiv1\pmodn
n
n
b\equiv\pm1\pmodn
For any composite
n
b
n
n
b
| k | |
| \prod | |
| i=1 |
\gcd(pi-1,n-1)
p1,...,pk
n
For example, for
n=341=11 ⋅ 31
\gcd(10,340) ⋅ \gcd(30,340)=100
n=341
b=2
Every odd composite
n
n
n
For composite n < 200, the following is a table of all bases b < n which n is a Fermat pseudoprime. If a composite number n is not in the table (or n is in the sequence), then n is a pseudoprime only to the trivial base 1 modulo n.
| n | bases b to which n is a Fermat pseudoprime (< n) | number of the bases of b (< n) | |
| 9 | 1, 8 | 2 | |
| 15 | 1, 4, 11, 14 | 4 | |
| 21 | 1, 8, 13, 20 | 4 | |
| 25 | 1, 7, 18, 24 | 4 | |
| 27 | 1, 26 | 2 | |
| 28 | 1, 9, 25 | 3 | |
| 33 | 1, 10, 23, 32 | 4 | |
| 35 | 1, 6, 29, 34 | 4 | |
| 39 | 1, 14, 25, 38 | 4 | |
| 45 | 1, 8, 17, 19, 26, 28, 37, 44 | 8 | |
| 49 | 1, 18, 19, 30, 31, 48 | 6 | |
| 51 | 1, 16, 35, 50 | 4 | |
| 52 | 1, 9, 29 | 3 | |
| 55 | 1, 21, 34, 54 | 4 | |
| 57 | 1, 20, 37, 56 | 4 | |
| 63 | 1, 8, 55, 62 | 4 | |
| 65 | 1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64 | 16 | |
| 66 | 1, 25, 31, 37, 49 | 5 | |
| 69 | 1, 22, 47, 68 | 4 | |
| 70 | 1, 11, 51 | 3 | |
| 75 | 1, 26, 49, 74 | 4 | |
| 76 | 1, 45, 49 | 3 | |
| 77 | 1, 34, 43, 76 | 4 | |
| 81 | 1, 80 | 2 | |
| 85 | 1, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 84 | 16 | |
| 87 | 1, 28, 59, 86 | 4 | |
| 91 | 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90 | 36 | |
| 93 | 1, 32, 61, 92 | 4 | |
| 95 | 1, 39, 56, 94 | 4 | |
| 99 | 1, 10, 89, 98 | 4 | |
| 105 | 1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104 | 16 | |
| 111 | 1, 38, 73, 110 | 4 | |
| 112 | 1, 65, 81 | 3 | |
| 115 | 1, 24, 91, 114 | 4 | |
| 117 | 1, 8, 44, 53, 64, 73, 109, 116 | 8 | |
| 119 | 1, 50, 69, 118 | 4 | |
| 121 | 1, 3, 9, 27, 40, 81, 94, 112, 118, 120 | 10 | |
| 123 | 1, 40, 83, 122 | 4 | |
| 124 | 1, 5, 25 | 3 | |
| 125 | 1, 57, 68, 124 | 4 | |
| 129 | 1, 44, 85, 128 | 4 | |
| 130 | 1, 61, 81 | 3 | |
| 133 | 1, 8, 11, 12, 18, 20, 26, 27, 30, 31, 37, 39, 45, 46, 50, 58, 64, 65, 68, 69, 75, 83, 87, 88, 94, 96, 102, 103, 106, 107, 113, 115, 121, 122, 125, 132 | 36 | |
| 135 | 1, 26, 109, 134 | 4 | |
| 141 | 1, 46, 95, 140 | 4 | |
| 143 | 1, 12, 131, 142 | 4 | |
| 145 | 1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144 | 16 | |
| 147 | 1, 50, 97, 146 | 4 | |
| 148 | 1, 121, 137 | 3 | |
| 153 | 1, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 152 | 16 | |
| 154 | 1, 23, 67 | 3 | |
| 155 | 1, 61, 94, 154 | 4 | |
| 159 | 1, 52, 107, 158 | 4 | |
| 161 | 1, 22, 139, 160 | 4 | |
| 165 | 1, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 164 | 16 | |
| 169 | 1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168 | 12 | |
| 171 | 1, 37, 134, 170 | 4 | |
| 172 | 1, 49, 165 | 3 | |
| 175 | 1, 24, 26, 51, 74, 76, 99, 101, 124, 149, 151, 174 | 12 | |
| 176 | 1, 49, 81, 97, 113 | 5 | |
| 177 | 1, 58, 119, 176 | 4 | |
| 183 | 1, 62, 121, 182 | 4 | |
| 185 | 1, 6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179, 184 | 16 | |
| 186 | 1, 97, 109, 157, 163 | 5 | |
| 187 | 1, 67, 120, 186 | 4 | |
| 189 | 1, 55, 134, 188 | 4 | |
| 190 | 1, 11, 61, 81, 101, 111, 121, 131, 161 | 9 | |
| 195 | 1, 14, 64, 79, 116, 131, 181, 194 | 8 | |
| 196 | 1, 165, 177 | 3 |
For more information (n = 201 to 5000), see,[9] this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n). When p is a prime, p2 is a Fermat pseudoprime to base b if and only if p is a Wieferich prime to base b. For example, 10932 = 1194649 is a Fermat pseudoprime to base 2, and 112 = 121 is a Fermat pseudoprime to base 3.
The number of the values of b for n are (For n prime, the number of the values of b must be n - 1, since all b satisfy the Fermat little theorem)
1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ...
The least base b > 1 which n is a pseudoprime to base b (or prime number) are
2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ...
The number of the values of b for n must divides \varphi
(n), or (n) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (The quotient can be any natural number, and the quotient = 1 if and only if n is a prime or a Carmichael number (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ...), the quotient = 2 if and only if n is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ...)
The least number with n values of b are (or 0 if no such number exists)
1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (if and only if n is even and not totient of squarefree number, then the nth term of this sequence is 0)
A composite number n which satisfy that
bn\equivb\pmodn
4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ...
All terms are less than or equal to the smallest Carmichael number, 561. Except for 561, only semiprimes can occur in the above sequence, but not all semiprimes less than 561 occur, a semiprime pq (p ≤ q) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) is also usually semiprime, the first counterexample is (648) = 385 = 5 × 7 × 11.
If we require n > b, they are (for b = 1, 2, ...)
4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ...
Carmichael numbers are weak pseudoprimes to all bases.
The smallest even weak pseudoprime in base 2 is 161038 (see).
See main article: Euler–Jacobi pseudoprime. Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler–Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay–Strassen primality test, the Baillie–PSW primality test, and the Miller–Rabin primality test, which produce what are known as industrial-grade primes. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure.
The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.