Número pseudoprimo de Fermat
# Número pseudoprimo de Fermat

Un número entero compuesto x se denomina pseudoprimo de Fermat respecto a la base de exponenciación entera a > 1, si x es divisor de $(a^{x−1}$ − $1).^{:Def.3.32}$ El pequeño teorema de Fermat establece que si p es primo y a es coprimo con respecto a p, entonces $(a^{p−1}$ − 1) es divisible por p.

En otras palabras, un entero compuesto es un pseudoprimo de Fermat respecto a la base a si satisface el test de primalidad de Fermat para la base a. La declaración falsa de que todos los números que pasan la prueba de primalidad de Fermat para la base 2 son primos, se llama hipótesis china.

En teoría de números, los pseudoprimos de Fermat constituyen la clase más importante de números pseudoprimos que provienen de Pequeño teorema de Fermat.

## Denominaciones

Los pseudoprimos en base de exponenciación 2 a veces se denominan números de Sarrus, por P. F. Sarrus, que descubrió que 341 tiene esta propiedad; números de Poulet, por P. Poulet, que hizo una tabla de tales números, o fermatianos por Pierre de Fermat (sucesión A001567 en OEIS).

Un pseudoprimo de Fermat a menudo se denomina simplemente pseudoprimo, sobreentendiéndose el modificador de Fermat.

Un entero x que es un pseudoprimo de Fermat para todos los valores de a que son coprimos con x se denomina número de $Carmichael.^{:Def.3.34}$

## Ejemplo

El pseudoprimo de Fermat en base 2 más pequeño es 341. No es un primo, ya que es igual a 11·31, pero satisface el pequeño teorema de Fermat: $2^{340}$ ≡ 1 (mod 341) y por lo tanto satisface el test de primalidad de Fermat para la base 2.

## Propiedades

### Distribución

Hay infinitos pseudoprimos para cualquier base dada a > 1. En 1904, Cipolla demostró cómo producir un número infinito de pseudoprimos base a > 1: Sea p cualquier primo impar que no divide a $(a^2$ - 1). Sea A = $(a^p$ - 1)/(a - 1) y sea B = $(a^p$ + 1)/(a + 1). Entonces n = AB es compuesto, y es un pseudoprimo respecto a la base a. Por ejemplo, si a = 2 y p = 5, entonces A = 31, B = 11 y n = 341 es un pseudoprimo respecto a la base 2.

De hecho, hay infinitos número pseudoprimo fuerte en cualquier base mayor que 1 (véase el teorema 1 del libro The pseudoprimes to $25·10^9)$ e infinitamente muchos números de Carmichael, pero son comparativamente raros. Hay tres pseudoprimos en base 2 por debajo de 1000, 245 por debajo de un millón y 21853 por debajo de $25·10^9.$ Hay 4842 pseudoprimos fuertes de base 2 y 2163 números de Carmichael por debajo de este límite (consúltese la mencionada tabla 1).

A partir de 17·257, el producto de números de Fermat consecutivos es un pseudoprimo de base 2, al igual que todos los compuestos de Fermat y los compuestos de Mersenne.

### Factorizaciones

Las factorizaciones de los 60 números de Poulet hasta 60787, incluidos los 13 números de Carmichael (en negrita), se encuentran en la siguiente tabla.

(sucesión A001567 en OEIS)

(Poulet de 1 hasta 15) :

| 341 | 11 · 31 |
| - | - |
| 561 | 3 · 11 · 17 |
| 645 | 3 · 5 · 43 |
| 1105 | 5 · 13 · 17 |
| 1387 | 19 · 73 |
| 1729 | 7 · 13 · 19 |
| 1905 | 3 · 5 · 127 |
| 2047 | 23 · 89 |
| 2465 | 5 · 17 · 29 |
| 2701 | 37 · 73 |
| 2821 | 7 · 13 · 31 |
| 3277 | 29 · 113 |
| 4033 | 37 · 109 |
| 4369 | 17 · 257 |
| 4371 | 3 · 31 · 47 |

(Poulet de 16 hasta 30) :

| 4681 | 31 · 151 |
| - | - |
| 5461 | 43 · 127 |
| 6601 | 7 · 23 · 41 |
| 7957 | 73 · 109 |
| 8321 | 53 · 157 |
| 8481 | 3 · 11 · 257 |
| 8911 | 7 · 19 · 67 |
| 10261 | 31 · 331 |
| 10585 | 5 · 29 · 73 |
| 11305 | 5 · 7 · 17 · 19 |
| 12801 | 3 · 17 · 251 |
| 13741 | 7 · 13 · 151 |
| 13747 | 59 · 233 |
| 13981 | 11 · 31 · 41 |
| 14491 | 43 · 337 |

(Poulet de 31 hasta 45) :

| 15709 | 23 · 683 |
| - | - |
| 15841 | 7 · 31 · 73 |
| 16705 | 5 · 13 · 257 |
| 18705 | 3 · 5 · 29 · 43 |
| 18721 | 97 · 193 |
| 19951 | 71 · 281 |
| 23001 | 3 · 11 · 17 · 41 |
| 23377 | 97 · 241 |
| 25761 | 3 · 31 · 277 |
| 29341 | 13 · 37 · 61 |
| 30121 | 7 · 13 · 331 |
| 30889 | 17 · 23 · 79 |
| 31417 | 89 · 353 |
| 31609 | 73 · 433 |
| 31621 | 103 · 307 |

(Poulet de 46 hasta 60) :

| 33153 | 3 · 43 · 257 |
| - | - |
| 34945 | 5 · 29 · 241 |
| 35333 | 89 · 397 |
| 39865 | 5 · 7 · 17 · 67 |
| 41041 | 7 · 11 · 13 · 41 |
| 41665 | 5 · 13 · 641 |
| 42799 | 127 · 337 |
| 46657 | 13 · 37 · 97 |
| 49141 | 157 · 313 |
| 49981 | 151 · 331 |
| 52633 | 7 · 73 · 103 |
| 55245 | 3 · 5 · 29 · 127 |
| 57421 | 7 · 13 · 631 |
| 60701 | 101 · 601 |
| 60787 | 89 · 683 |

Un número de Poulet cuyos divisores d dividen a $(2^d$ − 2) se llama supernúmero de Poulet. Hay infinitos números de Poulet que no son supernúmeros de Poulet.

### Pseudoprimos de Fermat más pequeños

El pseudoprimo (p-p) más pequeño para cada base a ≤ 200 se da en la siguiente tabla; los colores marcan el número de factores primos. A diferencia de la definición al comienzo del artículo, los pseudoprimos por debajo de a están excluidos de la tabla (para los pseudoprimos por debajo de a, véase (sucesión A090086 en OEIS)).

La tabla siguiente está basada en la (sucesión A007535 en OEIS)

| a | menor p-p | a | menor p-p | a | menor p-p | a | menor 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 |

### Lista de pseudoprimos de Fermat en base fija n

| n | Primeros pseudoprimos de Fermat en base n | Secuencia OEIS |
| - | - | - |
| 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) | (sucesión A002808 en OEIS) |
| 2 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... | (sucesión A001567 en OEIS) |
| 3 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... | (sucesión A005935 en OEIS) |
| 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, ... | (sucesión A020136 en OEIS) |
| 5 | 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... | (sucesión A005936 en OEIS) |
| 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, ... | (sucesión A005937 en OEIS) |
| 7 | 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... | (sucesión A005938 en OEIS) |
| 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, ... | (sucesión A020137 en OEIS) |
| 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, ... | (sucesión A020138 en OEIS) |
| 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, ... | (sucesión A005939 en OEIS) |
| 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, ... | (sucesión A020139 en OEIS) |
| 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, ... | (sucesión A020140 en OEIS) |
| 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, ... | (sucesión A020141 en OEIS) |
| 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, ... | (sucesión A020142 en OEIS) |
| 15 | 14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... | (sucesión A020143 en OEIS) |
| 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, ... | (sucesión A020144 en OEIS) |
| 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, ... | (sucesión A020145 en OEIS) |
| 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, ... | (sucesión A020146 en OEIS) |
| 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, ... | (sucesión A020147 en OEIS) |
| 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, ... | (sucesión A020148 en OEIS) |
| 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, ... | (sucesión A020149 en OEIS) |
| 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, ... | (sucesión A020150 en OEIS) |
| 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, ... | (sucesión A020151 en OEIS) |
| 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, ... | (sucesión A020152 en OEIS) |
| 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, ... | (sucesión A020153 en OEIS) |
| 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, ... | (sucesión A020154 en OEIS) |
| 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, ... | (sucesión A020155 en OEIS) |
| 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, ... | (sucesión A020156 en OEIS) |
| 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, ... | (sucesión A020157 en OEIS) |
| 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, ... | (sucesión A020158 en OEIS) |

Para obtener más información (base 31 a 100), consúltese (sucesión A020159 en OEIS) a (sucesión A020228 en OEIS), y para todas las bases hasta 150, consúltese la tabla de pseudoprimos de Fermat (texto en alemán), que no define n como pseudoprimo respecto con una base congruente con 1 o -1 (mod n).

## ¿Qué bases b hacen que n sea un pseudoprimo de Fermat?

Si el compuesto $n$ es par, entonces $n$ es un pseudoprimo de Fermat con la base trivial $b\equiv 1{\pmod {n}}$.

Si el compuesto $n$ es impar, entonces $n$ es un pseudoprimo de Fermat con las bases triviales $b\equiv \pm 1{\pmod {n}}$.

Para cualquier $n$ compuesto, el número de bases distintas $b$ módulo $n$, para las cuales $n$ es una base pseudoprima de Fermat $b$, $es^{:Thm.1,p.1392}$

    $\prod _{i=1}^{k}\gcd(p_{i}-1,n-1)$

donde $p_{1},\dots ,p_{k}$ son los distintos factores primos de $n$. Aquí se incluyen las bases triviales.

Por ejemplo, para $n=341=11\cdot 31$, este producto es $\gcd(10,340)\cdot \gcd(30,340)=100$. Para $n=341$, la base no trivial más pequeña es $b=2$.

Todo compuesto impar $n$ es un pseudoprimo de Fermat con al menos dos bases no triviales módulo $n$, a menos que $n$ sea una potencia de $3.^{:Cor.1,p.1393}$

Para los compuestos n < 200, la siguiente es una tabla de todas las bases b < n donde n es un pseudoprimo de Fermat. Si un número compuesto n no está en la tabla (o n está en la secuencia (sucesión A209211 en OEIS)), entonces n es un pseudoprimo solo para la base trivial 1 módulo n:

| n | Bases b en las que n es un pseudoprimo de Fermat (< n) | Número de las bases b (< n) (sucesión A063994 en OEIS) |
| - | - | - |
| 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 |

Para obtener más información (n = 201 a 5000), consúltese Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999). Esta página no define que n sea un pseudoprimo respecto a una base congruente con 1 o -1 (mod n). Cuando p es un primo, $p^2$ es un pseudoprimo de Fermat respecto a la base b si y solo si p es un número primo de Wieferich respecto a la base b. Por ejemplo, $1093^2$ = 1194649 es un pseudoprimo de Fermat en base 2 y $11^2$ = 121 es un pseudoprimo de Fermat en base 3.

El número de valores de b para n es (para n primo, el número de valores de b debe ser n - 1, ya que todo b satisface el pequeño teorema de Fermat):

    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, ... (sucesión A063994 en OEIS)

Las menores bases b > 1 para las que n es un pseudoprimo en base b (o número primo) son:

    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, ... (sucesión A105222 en OEIS)

El número de los valores de b para n debe dividir $\varphi$(n), o (sucesión A000010 en OEIS) (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, ... (el cociente puede ser cualquier número natural, y el cociente = 1 si y solo si n es un número primo o un número de Carmichael (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... (sucesión A002997 en OEIS)), el cociente = 2 si y solo si n está en la secuencia: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... (sucesión A191311 en OEIS))

Los menores números con n valores de b son (o 0 si no existe tal número):

    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, ... (sucesión A064234 en OEIS) (si y solo si n es par y no es un totiente libre de cuadrados, entonces el término n de esta secuencia es 0).

## Pseudoprimos débiles

Un número compuesto n que satisface que $b^{n}\equiv b{\pmod {n}}$ se llama pseudoprimo débil en base b. Un pseudoprimo bajo la definición usual satisface esta condición. Por el contrario, un pseudoprimo débil que es coprimo con la base es un pseudoprimo en el sentido habitual; de lo contrario, este puede ser el caso o no. Los menores pseudoprimos débiles en base b = 1, 2, ... son:

    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, ... (sucesión A000790 en OEIS)

Todos los términos son menores o iguales al número de Carmichael más pequeño, 561. Excepto por 561, solo pueden aparecer números semiprimos en la secuencia anterior, pero no todos los semiprimos menores que 561 aparecen. Un semiprimo pq (p ≤ q) menor que 561 aparece en las secuencias anteriores si y solo si (p − 1) divide a (q − 1) (véase (sucesión A108574 en OEIS)) Además, el pseudoprimo más pequeño respecto a la base n (también no es necesario exceder n) (Plantilla:Oeis) también suele ser semiprimo, el primer contraejemplo es (sucesión A090086 en OEIS)(648) = 385 = 5 × 7 × 11.

Si se requiere que n > b, son (para 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, ... (sucesión A239293 en OEIS)

Los números de Carmichael son pseudoprimos débiles para todas las bases.

El pseudoprimo más pequeño, incluso débil, en base 2 es 161038 (véase (sucesión A006935 en OEIS)).

## Pseudoprimos de Euler-Jacobi

Otro enfoque es utilizar nociones más refinadas de pseudoprimalidad, como por ejemplo la de número pseudoprimo fuerte o número pseudoprimo de Euler-Jacobi, para los cuales no existen análogos de los números de Carmichael. Esto conduce a algoritmos probabilisticos como el test de Solovay-Strassen, el test de primalidad de Baillie-PSW y el test de primalidad de Miller-Rabin, que producen lo que se conoce como números primos de grado industrial, que son números enteros para los que la primalidad no ha sido "certificada" (es decir, probada rigurosamente), pero se han sometido a una prueba como la prueba de Miller-Rabin que tiene una probabilidad de falla distinta de cero, pero arbitrariamente baja.

## Aplicaciones

La rareza de estos pseudoprimos tiene importantes implicaciones prácticas. Por ejemplo, los algoritmos de criptografía asimétrica como el RSA requieren la capacidad de encontrar números primos grandes rápidamente. El algoritmo habitual para generar números primos es generar números impares aleatorios y someter a prueba su primalidad. Sin embargo, las pruebas de primalidad determinísticas son lentas. Si el usuario está dispuesto a tolerar una posibilidad arbitrariamente pequeña de que el número encontrado no sea un número primo sino un pseudoprimo, es posible utilizar el test de primalidad de Fermat, mucho más rápido y sencillo.

