In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.
Definition Fermat's little theorem states that if is prime and is coprime to , then is divisible by . For a positive integer , if a composite integer divides then is called a Fermat pseudoprime to base .
In other words, a composite integer is a Fermat pseudoprime to base if it successfully passes the Fermat primality test for the base . 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: and thus passes the Fermat 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 that is a Fermat pseudoprime for all values of that are coprime to is called a Carmichael number.
Properties
Distribution There are infinitely many pseudoprimes to any given base . In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base : let and let , where is a prime number that does not divide . Then is composite, and is a pseudoprime to base . For example, if and , then , , and is a pseudoprime to base .
In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of ) and infinitely many Carmichael numbers, 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 ).
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 . Specifically, Kim and Pomerance showed the following: The probability that a random odd number is a Fermat pseudoprime to a random base is less than 2.77·10−8 for x= 10100, and is at most (log x)−197<10−10,000 for x≥10100,000. For a fixed base b, the proportion of pseudoprimes up to x is at most e-log x log log log x/(2 log log x) for large x. Pomerance as quoted in , section 2.1.
Factorizations The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table.
+ Poulet 1 to 1534111 · 315613 · 11 · 176453 · 5 · 4311055 · 13 · 17138719 · 7317297 · 13 · 1919053 · 5 · 127204723 · 8924655 · 17 · 29270137 · 7328217 · 13 · 31327729 · 113403337 · 109436917 · 25743713 · 31 · 47+ Poulet 16 to 30468131 · 151546143 · 12766017 · 23 · 41795773 · 109832153 · 15784813 · 11 · 25789117 · 19 · 671026131 · 331105855 · 29 · 73113055 · 7 · 17 · 19128013 · 17 · 251137417 · 13 · 1511374759 · 2331398111 · 31 · 411449143 · 337+ Poulet 31 to 451570923 · 683158417 · 31 · 73167055 · 13 · 257187053 · 5 · 29 · 431872197 · 1931995171 · 281230013 · 11 · 17 · 412337797 · 241257613 · 31 · 2772934113 · 37 · 61301217 · 13 · 3313088917 · 23 · 793141789 · 3533160973 · 43331621103 · 307+ Poulet 46 to 60331533 · 43 · 257349455 · 29 · 2413533389 · 397398655 · 7 · 17 · 67410417 · 11 · 13 · 41416655 · 13 · 64142799127 · 3374665713 · 37 · 9749141157 · 31349981151 · 331526337 · 73 · 103552453 · 5 · 29 · 127574217 · 13 · 63160701101 · 6016078789 · 683
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.
Smallest Fermat pseudoprimes 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
List of Fermat pseudoprimes in fixed base n