Псевдопросто Ферма

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

Определение [ править ]

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

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

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

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

Целое число x, которое является псевдопростом Ферма для всех значений a , взаимно простых с x , называется числом Кармайкла . ^[2]^[1]^{: По умолчанию. 3,34}

Свойства [ править ]

Распространение [ править ]

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

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

Начиная с 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,23
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, называется числом Суперпуле . Существует бесконечно много чисел Пуле, которые не являются числами суперпуле. ^[6]

Наименьшие псевдопреступности Ферма [ править ]

Наименьшее псевдопростое число для каждого основания 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 {п}}}$

Для любого композиционного материала , то число из различных баз по модулю , для которых является базой псевдопростого числа Ферма , является ^[7]^:^Thm.^{1, стр.}¹³⁹² ${\ 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. ^[7]^:^Кор.^{1, стр.}¹³⁹³ ${\ 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) см. ^[8], эта страница не определяет, что 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 φ {\ displaystyle \ varphi} находится в последовательности: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311 )

Наименьшее число с 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 (согласно обычному определению). И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростом в обычном смысле слова, иначе это может быть, а может и не быть. ^[9] Наименее слабые псевдопростые числа по основанию 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, требуют способности быстро находить большие простые числа. Обычный алгоритм генерации простых чисел заключается в генерации случайных нечетных чисел и проверке их на простоту. Однако детерминированные тесты на простоту выполняются медленно. Если пользователь готов допустить сколь угодно малую вероятность того, что найденное число является не простым числом, а псевдопростом, можно использовать гораздо более быстрый и простой тест на простоту Ферма .

Ссылки [ править ]

^ a b Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-1-4704-1048-3.
^ a b Desmedt, Иво (2010). «Схемы шифрования» . В Аталлахе Михаил Дж .; Блэнтон, Марина (ред.). Справочник по алгоритмам и теории вычислений: Специальные темы и методы . CRC Press. С. 10–23. ISBN 978-1-58488-820-8.
^ Пауло Рибенбоим (1996). Новая книга рекордов простых чисел . Нью-Йорк: Springer-Verlag . п. 108. ISBN 0-387-94457-5.
^ a b Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С., младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 .
^ Alford, WR ; Гранвиль, Эндрю ; Померанс, Карл (1994). «Есть бесконечно много чисел Кармайкла» (PDF) . Анналы математики . 140 (3): 703–722. DOI : 10.2307 / 2118576 . JSTOR 2118576 .
^ Серпинского, W. (1988-02-15), "Глава V.7", в ред. А. Шинцель (ред.), Элементарная теория чисел , Математическая библиотека Северной Голландии (2-е изд.), Амстердам: Северная Голландия, стр. 232, ISBN 9780444866622
^ а б Роберт Бэйли; Сэмюэл С. Вагстафф младший (октябрь 1980 г.). «Лукас Псевдопреступления» (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . Руководство по ремонту 0583518 .
^ "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) - Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher" . de.m.wikibooks.org . Проверено 21 апреля 2018 года .
^ Мишон, Джерард. «Псевдопростые числа, Слабые псевдопредставления, Сильные псевдопредставления, Простое число - Численное» . www.numericana.com . Проверено 21 апреля 2018 года .

Внешние ссылки [ править ]

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

[JoyOfFactoring-1] Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-1-4704-1048-3.

[desmedt-10-23-2] Desmedt, Иво (2010). «Схемы шифрования» . В Аталлахе Михаил Дж .; Блэнтон, Марина (ред.). Справочник по алгоритмам и теории вычислений: Специальные темы и методы . CRC Press. С. 10–23. ISBN 978-1-58488-820-8.

[3] Пауло Рибенбоим (1996). Новая книга рекордов простых чисел . Нью-Йорк: Springer-Verlag . п. 108. ISBN 0-387-94457-5.

[PSW-4] Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С., младший (июль 1980 г.). «Псевдопреступности до 25 · 10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. DOI : 10.1090 / S0025-5718-1980-0572872-7 .

[Alford1994-5] Alford, WR ; Гранвиль, Эндрю ; Померанс, Карл (1994). «Есть бесконечно много чисел Кармайкла» (PDF) . Анналы математики . 140 (3): 703–722. DOI : 10.2307 / 2118576 . JSTOR 2118576 .

[6] Серпинского, W. (1988-02-15), "Глава V.7", в ред. А. Шинцель (ред.), Элементарная теория чисел , Математическая библиотека Северной Голландии (2-е изд.), Амстердам: Северная Голландия, стр. 232, ISBN 9780444866622

[lpsp-7] а б Роберт Бэйли; Сэмюэл С. Вагстафф младший (октябрь 1980 г.). «Лукас Псевдопреступления» (PDF) . Математика вычислений . 35 (152): 1391–1417. DOI : 10.1090 / S0025-5718-1980-0583518-6 . Руководство по ремонту 0583518 .

[8] "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) - Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher" . de.m.wikibooks.org . Проверено 21 апреля 2018 года .

[9] Мишон, Джерард. «Псевдопростые числа, Слабые псевдопредставления, Сильные псевдопредставления, Простое число - Численное» . www.numericana.com . Проверено 21 апреля 2018 года .

[1]