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 Plantilla:Nowrap.Plantilla:Rp El pequeño teorema de Fermat establece que si p es primo y a es coprimo con respecto a p, entonces Plantilla:Nowrap 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 Plantilla: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.Plantilla:Rp

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³⁴⁰ ≡ 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² - 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⁹) 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⁹. 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.

Plantilla:Nowrap 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

Plantilla:Nowrap 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

Plantilla:Nowrap 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

Plantilla:Nowrap 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 Plantilla:OEIS).

La tabla siguiente está basada en la Plantilla: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)	Plantilla:OEIS
2	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla:OEIS
5	4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...	Plantilla: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, ...	Plantilla:OEIS
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla:OEIS
15	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla: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, ...	Plantilla:OEIS

Para obtener más información (base 31 a 100), consúltese Plantilla:OEIS a Plantilla: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(\mathrm{mod}n)$.

Si el compuesto $n$ es impar, entonces $n$ es un pseudoprimo de Fermat con las bases triviales $b\equiv \pm 1(\mathrm{mod}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$, esPlantilla:Rp

$\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.Plantilla:Rp

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 Plantilla: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) Plantilla: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² 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² = 1194649 es un pseudoprimo de Fermat en base 2 y 11² = 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, ... Plantilla: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, ... Plantilla:OEIS

El número de los valores de b para n debe dividir $\phi$(n), o Plantilla: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, ... Plantilla:OEIS), el cociente = 2 si y solo si n está en la secuencia: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... Plantilla: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, ... Plantilla: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(\mathrm{mod}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, ... Plantilla: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 Plantilla: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 Plantilla: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, ... Plantilla: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 Plantilla: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.

Enlaces externos

• W. F. Galway and Jan Feitsma, Tables of pseudoprimes to base 2 and related data (comprehensive list of all pseudoprimes to base 2 below 2⁶⁴, including factorization, strong pseudoprimes, and Carmichael numbers)
• Investigación sobre pseudoprimos