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).^[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.^[2] 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[editar]

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.^[2]^[1]^{: Def. 3.34}

Ejemplo[editar]

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[editar]

Distribución[editar]

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.^[3] 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⁹^[4]) e infinitamente muchos números de Carmichael,^[5] 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).^[4]

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[editar]

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.^[6]

Pseudoprimos de Fermat más pequeños[editar]

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[editar]

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?[editar]

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^[7]^{: 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.^[7]^{: 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).^[8] 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, ... (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[editar]

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.^[9] 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) ((sucesión A090086 en 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[editar]

Artículo principal: Número pseudoprimo 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[editar]

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.

Referencias[editar]

↑ ^a ^b Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.
↑ ^a ^b Desmedt, Yvo (2010). «Encryption Schemes». En Atallah, Mikhail J.; Blanton, Marina, eds. Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10-23. ISBN 978-1-58488-820-8.
↑ Paulo Ribenboim (1996). The New Book of Prime Number Records. New York: Springer Science+Business Media. p. 108. ISBN 0-387-94457-5.
↑ ^a ^b Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S. Jr. (July 1980). «The pseudoprimes to 25·10⁹». Mathematics of Computation 35 (151): 1003-1026. doi:10.1090/S0025-5718-1980-0572872-7.
↑ Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). «There are Infinitely Many Carmichael Numbers». Annals of Mathematics 140 (3): 703-722. JSTOR 2118576. doi:10.2307/2118576.
↑ Sierpinski, W. (15 de febrero de 1988), «Chapter V.7», en Ed. A. Schinzel, ed., Elementary Theory of Numbers, North-Holland Mathematical Library (2 Sub edición), Amsterdam: North Holland, p. 232, ISBN 9780444866622 .
↑ ^a ^b Robert Baillie; Samuel S. Wagstaff Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.
↑ «Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher». de.m.wikibooks.org. Consultado el 21 de abril de 2018.
↑ Michon, Gerard. «Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality - Numericana». www.numericana.com. Consultado el 21 de abril de 2018.

Enlaces externos[editar]

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

Datos: Q1406394

[JoyOfFactoring-1] Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN 978-1-4704-1048-3.

[desmedt-10-23-2] Desmedt, Yvo (2010). «Encryption Schemes». En Atallah, Mikhail J.; Blanton, Marina, eds. Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10-23. ISBN 978-1-58488-820-8.

[3] Paulo Ribenboim (1996). The New Book of Prime Number Records. New York: Springer Science+Business Media. p. 108. ISBN 0-387-94457-5.

[PSW-4] Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S. Jr. (July 1980). «The pseudoprimes to 25·10⁹». Mathematics of Computation 35 (151): 1003-1026. doi:10.1090/S0025-5718-1980-0572872-7.

[Alford1994-5] Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). «There are Infinitely Many Carmichael Numbers». Annals of Mathematics 140 (3): 703-722. JSTOR 2118576. doi:10.2307/2118576.

[6] Sierpinski, W. (15 de febrero de 1988), «Chapter V.7», en Ed. A. Schinzel, ed., Elementary Theory of Numbers, North-Holland Mathematical Library (2 Sub edición), Amsterdam: North Holland, p. 232, ISBN 9780444866622 .

[lpsp-7] Robert Baillie; Samuel S. Wagstaff Jr. (October 1980). «Lucas Pseudoprimes». Mathematics of Computation 35 (152): 1391-1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.

[8] «Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher». de.m.wikibooks.org. Consultado el 21 de abril de 2018.

[9] Michon, Gerard. «Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality - Numericana». www.numericana.com. Consultado el 21 de abril de 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]