페르마 유사성

수 이론에서 페르마의 작은 정리에서 오는 가장 중요한 부류의 유사시를 구성한다.

정의

페르마의 작은 정리는 p가 프라임이고 a가 p와 짝짓기라면 a^p−1 - 1은 p로 나누어진다. 정수 a > 1의 경우, 합성 정수 x가 a^x−1 - 1을 나누면, x를 Fermat 유사점이라고 하여 a를 베이스로 한다. ^{[1]: Def. 3.32} 즉, 복합정수는 기초 a에 대한 Fermat 원시성 시험을 성공적으로 통과하면 기초 a를 기초로 하는 Fermat 유사성이다.^[2] 염기 2에 대한 페르마 원시성 검정을 통과한 모든 숫자가 소수라는 거짓 진술을 중국 가설이라고 한다.

가장 작은 base-2 Fermat 유사점은 341이다. 11·31과 같기 때문에 프라임은 아니지만 페르마의 작은 정리인 2³⁴⁰≡ 1 (mod 341)을 만족시켜 베이스 2에 대한 페르마 프라임성 시험을 통과한다.

염기 2에 대한 가성비는 341이 이런 속성, 푸렛 번호를 가지고 있다는 것을 발견한 P. F. Sarrus의 이름을 따서 Sarrus number라고 부르기도 하고, 그러한 숫자의 표를 만든 P. Poulet의 이름을 따서 Fermatians(OEIS에서 연속 A001567)라고 부르기도 한다.

페르마 유사성(Fermat philoprime)은 종종 유사성(pseoprime)이라고 불리며, 수식어인 페르마(Fermat)가 이해되고 있다.

x에 대한 coprime인 a의 모든 값에 대한 Fermat 유사점인 정수 x를 Carmichael 숫자라고 한다.^{[2][1]: Def. 3.34}

특성.

분배

주어진 base a > 1에는 가성비가 무한히 많다. 1904년에 씨폴라는 무한히 많은 가성비를 생산하는 방법을 보여주었는데 a > 1: p를 - 1. A² = (a - 1)/(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 참조)와 카마이클 숫자들은 무한히 많은 강한 유사성들이 있지만,^[5] 그것들은 상대적으로 드물다. 베이스2는 1000 이하, 100만 이하 245회, 25·10 이하⁹ 21853회까지 가성비가 3회 있다. 이 제한보다 낮은 4842개의 강한 유사 시간 베이스 2와 2163 카마이클 숫자가 있다(의 표 1 참조).

17·257년부터 연속 페르마트 번호의 산물은 베이스-2 유사점이며, 페르마트 합성물과 메르센 합성물이 모두 그러하다.

인자화

카마이클 번호 13개(볼드체)를 포함하여 60787까지 60 Poulet 번호의 인자화는 다음 표에 있다.

(OEIS에서 시퀀스 A001567)

푸렛 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 · 113 4033 37 · 109 4369 17 · 257 4371 3 · 31 · 47

풀레1630 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

포울렛3145 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

포울렛4660 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 - 2의 분점을 가진 모든 분점 숫자를 슈퍼 분점 번호라고 부른다. 슈퍼 퍼플릿 번호가 아닌 퍼플릿 번호가 무한히 많다.^[6]

최소 페르마 유사수

각 베이스에 대한 최소 가성비 200은 다음 표에 제시되어 있다. 색상은 주요 인자의 수를 나타낸다. 기사 시작의 정의와 달리, 표에는 a 이하의 가성비는 제외된다. (그것은 a 이하의 가성비를 허용하려면, OEIS: A090086 참조)

(OEIS에서 시퀀스 A007535)

a	가장 작은 p-p	a	가장 작은 p-p	a	가장 작은 p-p	a	가장 작은 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

고정기반의 페르마 유사시 목록 n

n	처음 몇 번의 Fermat 유사점 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, ... (All composites)	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, ...	A02037
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, ...	A02018
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, ...	A02039
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개의 베이스에 대해서는 Fermat 유사 시간 표(독일어 텍스트)를 참조하십시오. 이 페이지에서는 n이 1 또는 -1(mod n)에 해당하는 베이스에 대한 유사 시간이라고 정의하지 않는다.

어떤 베이스 b가 n을 페르마 유사점프라임으로 만드는가?

If composite ${\displaystyle n}$ is even, then ${\displaystyle n}$ is a Fermat pseudoprime to the trivial base ${\displaystyle b\equiv 1{\pmod {n}}}$. If composite ${\displaystyle n}$ is odd, then ${\displaystyle n}$ is a Fermat pseudoprime to the trivial bases ${\$디스플레이 스타일 b$\equiv \pm$ 1${\pmod{n$

모든 $합성{\displaystyle }$ n$${\$displaystyle n$의 경우, 고유한 $b{\displaystyle }${\$displaystyle b}$$모듈$로 n$${\$displaystyle$ n$\}$의 개수는 다음과 같으며, $여기$서$$n {\$displaystyle$ n$\}$은$($는) Fermat $phascoprime{\displaystyle }$b {\$dystyle b}$이다.

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

여기서 $p{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$… ,${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ ${\$는 $n{\displaystyle }$ ${\displaystyle n}$의 고유한 주요 요인이다$.$ 여기에는 사소한 근거도 포함된다.

예를 들어, n${\displaystyle }$= ${\displaystyle 341}$= ${\displaystyle 11}$ ${\displaystyle \cdot }$ ${\displaystyle 31}$ ${\displaystyle n=341=11\cdot 31}$의 경우$,$ 이 제품은 ${\displaystyle gcd}$(${\displaystyle 10}$, ${\displaystyle 340}$) ${\displaystyle \cdot }$ ${\displaystyle gcd}$($30,340$ )${\displaystyle }$= ${\displaystyle 100}$ ${\displaystyle \gcd$(10$,340)\cdgcd(30,$340)=$100$ 입니다$.$ $n{\displaystyle }$= ${\displaystyle 341}$ ${\displaystyle n=341}$의 경우$,$ 이와 같은 최소 비경쟁 기반은 $b{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle b=2}$이다$.$

$모든{\displaystyle }$ 홀수 합성물$n{\displaystyle }$ {\$displaystyle$ $n$$}$은(는$)$ n {\$displaystyle$ n$}$이(가) 3의 검정력이 아닌$$$$ 한 최소 두 개의 비경쟁 베이스 $모듈$로 ${\displaystyle n}$에 대한 Fermat 유사 시간이다$$.^{[7]: Cor. 1, p. 1393}

복합 n < 200의 경우, 다음은 모든 베이스 b < n의 표로서, n은 페르마 유사점이다. 복합 숫자 n이 표에 없는 경우(또는 n이 A209211 시퀀스에 있는 경우), n은 사소한 기준 1 modulo n에만 가성비가 된다.

n	base b. n이 Fermat 유사점(<n)인 경우	b(<n)의 베이스 수 (OEIS에서 시퀀스 A063994)
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)의 기본 일치에 대한 가성비라고 정의하지 않음을 참조하십시오.^[8] p가 prime일 때 p는² b 베이스를 위한 wieferich 프라임인 경우에만 b 베이스를 위한 Fermat 유사점프라임이다. 예를 들어 1093² = 1194649는 베이스 2에 대한 페르마트 유사점이고, 11² = 121은 베이스 3에 대한 페르마트 유사점이다.

n에 대한 b의 값의 수는 다음과 같다(n prime의 경우, b의 값은 모두 페르마트의 작은 정리를 만족하므로 n - 1이어야 한다).

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, ... (sequence A063994 in the OEIS)

n이 base b(또는 prime number)에 대한 가성인 b > 1은 다음과 같다.

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, ... (sequence A105222 in the OEIS)

The number of the values of b for n must divides ${\displaystyle \varphi }$(n), or 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, ... (The quotient can be any natural number, and the quotient = 1 n이 프라임 또는 카마이클 번호인 경우(561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997), 지수 = 2 if and only n이 시퀀스인 경우: 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, ... (sequence A064234 in the OEIS) (if and only if n is even and not totient of squarefree number, then the nth te이 시퀀스의 rm은 0)

약한 유사성

$b{\displaystyle {}^{}}$ ${\displaystyle n^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle b}$( ${\displaystyle \mathrm{mod}}$ ${\displaystyle n}$) ${\$ b${\pmod{n}}}$을(를) 만족하는 합성수 n을 base b에 약한 유사수라고 한다$$. (일반적인 정의에 따라) a를 기초로 하는 가성비가 이 조건을 만족시킨다. 반대로, 베이스와 결합하는 약한 가성비는 통상적인 의미에서 가성비라고 할 수 있으며, 그렇지 않으면 이런 경우도 있을 수 있고 아닐 수도 있다.^[9] b = 1, 2, ...에 대한 가장 약한 가성비는 다음과 같다.

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, ... (sequence A000790 in the OEIS)

모든 항은 가장 작은 카마이클 수인 561보다 작거나 같다. Except for 561, only semiprimes can occur in the above sequence, but not all semiprimes less than 561 occur, a semiprime pq (p ≤ q) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see OEIS: A108574) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) (OEIS: A090086) is also usually semiprime, 첫 번째 counterexample은 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, ... (sequence A239293 in the OEIS)

카마이클 수치는 모든 베이스에 약한 유사배수다.

베이스 2에서 가장 작아도 약한 가성비는 161038이다(OEIS: A006935 참조).

오일러-자코비 유사시

또 다른 접근방법은 카마이클 숫자의 유사점이 없는 강한 유사 유사성 또는 오일러-자코비 유사성 등 보다 정제된 유사성 개념을 사용하는 것이다. 이로 인해 Solovay-Strassen 원시성 테스트, Baillie-와 같은 확률론적 알고리즘이 생성된다.산업용 프리타임으로 알려진 것을 생산하는 PSW 프라이머리티 테스트와 밀러-라빈 프라이머리티 테스트. 산업용 프리타임은 원시성이 "인증"되지 않은 정수(즉, 엄격하게 증명됨)로, 0은 아니지만 임의로 낮은 고장 확률을 갖는 밀러-라빈 시험과 같은 시험을 거쳤다.

적용들

그러한 유사시의 희귀성은 중요한 실제적 함의를 가지고 있다. 예를 들어 RSA와 같은 공개키 암호 알고리즘은 큰 프리마임을 신속하게 찾을 수 있는 기능이 필요하다. 소수점 생성을 위한 일반적인 알고리즘은 무작위 홀수를 생성하여 소수점 생성을 테스트하는 것이다. 그러나 결정론적 원시성 시험은 느리다. 사용자가 발견된 숫자가 소수만이 아니라 가성비라는 임의의 작은 가능성을 기꺼이 용인할 수 있다면 훨씬 빠르고 간단한 페르마 소수성 검사를 사용할 수 있다.

참조

외부 링크

• W. F. Galway 및 Jan Feitsma, 기초 2에 대한 유사 시간 표 및 관련 데이터(요인화, 강한 유사 시간 및 카마이클 숫자를 포함하여 기초 2에⁶⁴ 대한 모든 유사 시간 목록)
• 가성비를 위한 연구