Псевдоприм Ферма - Fermat pseudoprime

В теории чисел псевдопростые числа Ферма составляют наиболее важный класс псевдопростых чисел , которые вытекают из малой теоремы Ферма .

Определение

Малая теорема Ферма утверждает , что если р является простым и является взаимно просто с р , то ^{р -1}  - 1 делится на р . Для целого числа > 1, если составное целое число х делит ^{й -1}  - 1, то х называется псевдопростым числом Ферма к базовому а . Другими словами, составное целое число - это псевдопростое число Ферма для основания a, если оно успешно проходит тест на простоту Ферма для основания a . Ложное утверждение, что все числа, прошедшие тест на простоту Ферма по основанию 2, простые, называется китайской гипотезой .

Наименьшее псевдопростое число Ферма по основанию 2 - 341. Это не простое число, поскольку оно равно 11 · 31, но оно удовлетворяет малой теореме Ферма: 2 ³⁴⁰ ≡ 1 (mod 341) и, таким образом, проходит тест на простоту Ферма для основания 2.

Псевдопримеры с основанием 2 иногда называют числами Сарруса , в честь П. Ф. Сарруса, который обнаружил, что 341 обладает этим свойством, числами Пуле , в честь П. Пуле, который составил таблицу таких чисел, или ферматинцами (последовательность A001567 в OEIS ).

Псевдопростое число Ферма часто называют псевдопростом , причем подразумевается модификатор Ферма .

Целое число x, которое является псевдопростом Ферма для всех значений a , взаимно простых с x , называется числом Кармайкла .

Характеристики

Распределение

Есть бесконечное множество псевдопростое число в той или иной базовой а > 1. В 1904 году Cipolla показал , как производить бесконечное число псевдопростое число основывают > 1: Пусть р простое число , которое не поделить на ² - 1. Пусть А = ( а , ^p - 1) / ( a - 1) и пусть B = ( a ^p + 1) / ( a + 1). Тогда n = AB составно и является псевдопервичным числом для основания a . Например, если a = 2 и p = 5, то A = 31, B = 11 и n = 341 - псевдопростое число по основанию 2.

На самом деле существует бесконечно много сильных псевдопростых чисел с основанием больше 1 (см. Теорему 1 из) и бесконечно много чисел Кармайкла, но они сравнительно редки. Есть три псевдопростых числа для основания 2 меньше 1000, 245 меньше одного миллиона и 21853 меньше 25 · 10 ⁹ . Ниже этого предела имеется 4842 сильных псевдопростых числа с основанием 2 и 2163 числа Кармайкла (см. Таблицу 1).

Начиная с 17 · 257, продукт последовательных чисел Ферма является базой 2-псевдопростое число, и поэтому все Ферма композит и Мерсенн композита .

Факторизации

Факторизации 60 чисел Пуле до 60787, включая 13 чисел Кармайкла (выделены жирным шрифтом), приведены в следующей таблице.

(последовательность A001567 в OEIS )

Пулет от 1 до 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,13 4033 37 · 109 4369 17,257 4371 3,31,47

Пулет от 16 до 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

Пулет 31–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,43 31621 103 307

Пулет 46 на 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

Число Пуле, все делители d которого делят 2 ^d - 2, называется числом Суперпуле . Существует бесконечно много чисел Пуле, которые не являются числами суперпуле.

Наименьшие псевдопримеры Ферма

Наименьшее псевдопростое число для каждого основания a ≤ 200 приведено в следующей таблице; цвета обозначают количество простых множителей. В отличие от определения в начале статьи, псевдопространства ниже a исключаются из таблицы. (Чтобы разрешить псевдопределы ниже a , см. OEIS :  A090086 )

(последовательность A007535 в OEIS )

а	наименьший пп	а	наименьший пп	а	наименьший пп	а	наименьший пп
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

п	Первые несколько псевдопростых чисел Ферма в базе n	Последовательность 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, .. . (Все композиты)	A002808
2	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...	A001567
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...	A005935
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, ...	A020136
5	4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...	A005936
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, ...	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...	A005938
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, ...	A020137
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, ...	A020138
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, ...	A005939
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, ...	A020139
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, ...	A020140
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, ...	A020141
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, ...	A020142
15	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...	A020143
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, ...	A020144
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, ...	A020145
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, ...	A020146
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, ...	A020147
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, ...	A020148
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, .. .	A020149
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, ...	A020150
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, ...	A020151
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, ...	A020152
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, ...	A020153
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, ...	A020154
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, ...	A020155
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, ...	A020156
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, ...	A020157
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, ...	A020158

Для получения дополнительной информации (с основанием от 31 до 100) см. OEIS :  A020159 - OEIS :  A020228 , а для всех оснований до 150 см. Таблицу псевдопредставлений Ферма (текст на немецком языке) , на этой странице не определено, что n является псевдопростым числом по отношению к основанию. конгруэнтно 1 или -1 (mod n )

Какие основания b делают n псевдопростом Ферма?

Если композиция четная, то является псевдопервичным числом Ферма для тривиальной базы . Если композиция нечетна, то является псевдопервичным числом Ферма для тривиальных базисов . ${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle б \ эквив 1 {\ pmod {п}}}$${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle б \ эквив \ пм 1 {\ pmod {п}}}$

Для любого композиционного материала , то число из различных баз по модулю , для которых является база псевдопростого числа Ферма , является ${\ displaystyle n}$${\ displaystyle b}$${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle b}$

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

где различные простые делители . Сюда входят тривиальные основы. ${\ displaystyle p_ {1}, \ dots, p_ {k}}$${\ displaystyle n}$

Например, для этого товара есть . При наименьшей такой нетривиальной базе является . ${\ Displaystyle п = 341 = 11 \ cdot 31}$${\ Displaystyle \ НОД (10,340) \ CDOT \ НОД (30,340) = 100}$${\ displaystyle n = 341}$${\ displaystyle b = 2}$

Любая нечетная композиция является псевдопервичным числом Ферма по крайней мере для двух нетривиальных базисов по модулю, если не является степенью 3. ${\ displaystyle n}$${\ displaystyle n}$${\ displaystyle n}$

Для составного n <200, ниже приводится таблица всех оснований b < n, где n является псевдопростом Ферма. Если составного числа n нет в таблице (или n находится в последовательности A209211 ), то n является псевдопростом только для тривиального основания 1 по модулю n .

п	основания b, для которых n является псевдопервичным числом Ферма (< n )	количество оснований b (< n ) (последовательность A063994 в 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

Для получения дополнительной информации ( n = от 201 до 5000) см., Эта страница не определяет, что n является псевдопервичным основанием, равным 1 или -1 (mod n ). Когда p простое число, p ² является псевдопервичным числом Ферма по базе b тогда и только тогда, когда p является простым числом Вифериха с базой b . Например, 1093 ² = 1194649 - псевдопростое число Ферма по основанию 2, а 11 ² = 121 - псевдопростое число Ферма по основанию 3.

Количество значений b для n равно (для простого n количество значений b должно быть n - 1, поскольку все b удовлетворяют малой теореме Ферма )

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, ... (последовательность A063994 в OEIS )

Наименьшее основание b > 1, которое n является псевдопервичным основанием b (или простым числом), равно

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, ... (последовательность A105222 в OEIS )

Количество значений b для n должно делиться на ( n ), иначе A000010 ( 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, ... ( Частное может быть любым натуральным числом, а частное = 1 тогда и только тогда, когда n является простым или числом Кармайкла (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997 ), частное = 2 тогда и только тогда, когда n находится в последовательности: 4, 6, 15, 91, 703, 1891 , 2701, 11305, 12403, 13981, 18721, ... A191311 ) ${\ displaystyle \ varphi}$

Наименьшее число с n значениями b равно (или 0, если такого числа не существует)

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, ... (последовательность A064234 в OEIS ) ( тогда и только тогда , когда п является даже и не totient из бесквадратного числа , то п - й член этой последовательности равен 0)

Слабые псевдопремы

Составное число n, удовлетворяющее этому правилу, называется слабым псевдопервичным числом по основанию b . Псевдопервичное число в основе a (согласно обычному определению) удовлетворяет этому условию. И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростом в обычном смысле слова, иначе это может быть, а может и не быть. Наименее слабые псевдопростые числа по основанию b = 1, 2, ...: ${\ Displaystyle б ^ {п} \ эквив б {\ pmod {п}}}$

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, ... (последовательность A000790 в OEIS )

Все члены меньше или равны наименьшему числу Кармайкла, 561. За исключением 561, в приведенной выше последовательности могут встречаться только полупростые числа, но не все полупростые числа меньше 561, полупростое число pq ( p ≤ q ) меньше 561 встречается в приведенные выше последовательности тогда и только тогда, когда p - 1 делит q - 1. (см. OEIS :  A108574 ). Кроме того, наименьшее псевдопростое число по основанию n (также необязательно, превышающее n ) ( OEIS :  A090086 ) также обычно полупростое, первый контрпример A090086 (648) = 385 = 5 × 7 × 11.

Если нам потребуется n > b , они будут (для 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, ... (последовательность A239293 в OEIS )

Числа Кармайкла являются слабыми псевдопричинениями для всех оснований.

Наименьшее даже слабое псевдопростое число по основанию 2 - 161038 (см. OEIS :  A006935 ).

Псевдопримеры Эйлера – Якоби

Другой подход заключается в использовании более тонких понятий псевдопричинностей, например сильных псевдопростых чисел или псевдопростых чисел Эйлера – Якоби , для которых нет аналогов чисел Кармайкла . Это приводит к вероятностным алгоритмам , таким как тест-Соловея Штрассно на простоту , в тесте на простоту Бэйлей-PSW , и тест на простоту Миллер-Рабин , которые производят то , что известно как промышленный класс простых чисел . Простые числа промышленного уровня - это целые числа, для которых простота не была «сертифицирована» (т. Е. Строго доказана), но прошла тест, такой как тест Миллера – Рабина, который имеет ненулевую, но произвольно низкую вероятность отказа.

Приложения

Редкость таких псевдопреступлений имеет важное практическое значение. Например, алгоритмы шифрования с открытым ключом , такие как RSA, требуют способности быстро находить большие простые числа. Обычный алгоритм генерации простых чисел состоит в генерации случайных нечетных чисел и проверке их на простоту. Однако детерминированные тесты на простоту выполняются медленно. Если пользователь согласен допустить сколь угодно малую вероятность того, что найденное число не является простым числом, а псевдопростом, можно использовать гораздо более быстрый и простой тест на простоту Ферма .

Рекомендации

Внешние ссылки

• У. Ф. Голуэй и Ян Фейтсма, Таблицы псевдопростых чисел для базы 2 и связанных данных (исчерпывающий список всех псевдопростых чисел для базы 2 ниже 2 ⁶⁴ , включая факторизацию, сильные псевдопростые числа и числа Кармайкла)
• Исследование псевдопремий