费马伪素数

费马伪素数英語:)是指满足费马小定理伪素数,也是最重要的一类伪素数。

其定义是:对自然数和一个与其互素的自然数a,如果整除 ax-1 - 1,则称是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341=11×31,关于2)。如果关于任何与其互素的数都是费马伪素数,则称绝对伪素数(或卡邁克爾數,来自找到第一个绝对伪素数的数学家羅伯特·丹尼·卡邁克爾)。最小的绝对伪素数是561

有人已经证明了费马伪素数的个数是无穷的。有一位数学家如此评论:“对于素数,费马小定理肯定是正确的;但他没说在合数中就不正确。”事实上,费马小定理给出的是关于素数判定的必要不充分条件

另外,若:不是質數(如下表中的情況),則它就一定是偽質數。 這些當中包含了所有的費馬合數(當n=2k),梅森合數(當n=p)及瓦格斯塔夫合數(當n=2p)

分圓多項式階數n偽質數
112047=23x89
238388607=47x178481
251082401=601x1801
283277=29x113
29536870911=233x1103x2089
358727391=71x122921
364033=37x109
37137438953471=223x616318177
399588151=79x121369

费马伪素数年表

  • 1819年,萨鲁斯(Sarrus)发现第一个伪素数341
  • 1903年,马洛(Malo)证明:若n为伪素数,则也是一个伪素数,从而肯定了伪素数的个数是无穷的。
  • 1950年,发现第一个偶伪素数
  • 1951年,皮格(Beeger)证明了存在无限多个偶伪素数。

以2为底的前50个费马伪素数

OEIS數列A001567

nnnnn
1341 = 112821 = 218481 = 3115709 = 23 · 6834130121 = 7 · 13 · 331
2561 = 3 · 11 · 17123277 = 29 · 113228911 = 7 · 19 · 673215841 = 7 · 31 · 734230889 = 17 · 23 · 79
3645 = 3 · 5 · 43134033 = 37 · 1092310261 = 31 · 3313316705 = 5 · 13 · 2574331417 = 89 · 353
41105 = 5 · 13 · 17144369 = 17 · 2572410585 = 5 · 29 · 733418705 = 3 · 5 · 29 · 434431609 = 73 · 433
51387 = 19 · 73154371 = 3 · 31 · 472511305 = 5 · 7 · 17 · 193518721 = 97 · 1934531621 = 103 · 307
61729 = 7 · 13 · 19164681 = 31 · 1512612801 = 3 · 17 · 2513619951 = 71 · 2814633153 = 3 · 43 · 257
71905 = 3 · 5 · 127175461 = 43 · 1272713741 = 7 · 13 · 1513723001 = 3 · 11 · 17 · 414734945 = 5 · 29 · 241
82047 = 23 · 89186601 = 7 · 23 · 412813747 = 59 · 2333823377 = 97 · 2414835333 = 89 · 397
92465 = 5 · 17 · 29197957 = 73 · 1092913981 = 11 · 31 · 413925761 = 3 · 31 · 2774939865 = 5 · 7 · 17 · 67
102701 = 37 · 73208321 = 53 · 1573014491 = 43 · 3374029341 = 13 · 37 · 615041041 = 7 · 11 · 13 · 41

以任意整数为底的最小费马伪素数

OEIS數列A007535

a 最小的伪素数 a 最小的伪素数 a 最小的伪素数 a 最小的伪素数
1 4 = 51 65 = 5 · 13 101 175 = 151 175 =
2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19 152 153 =
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 = 55 63 = 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 = 57 65 = 5 · 13 107 133 = 7 · 19 157 186 = 2 · 3 · 31
8 9 = 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53
9 28 = 59 87 = 3 · 29 109 117 = 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 = 112 121 = 162 481 = 13 · 37
13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19 163 186 =
14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23 164 165 =
15 341 = 11 · 31 65 112 = 115 133 = 7 · 19 165 172 =
16 51 = 3 · 17 66 91 = 7 · 13 116 117 = 166 301 = 7 · 43
17 45 = 67 85 = 5 · 17 117 145 = 5 · 29 167 231 =
18 25 = 68 69 = 3 · 23 118 119 = 7 · 17 168 169 =
19 45 = 69 85 = 5 · 17 119 177 = 3 · 59 169 231 = 3 · 7 · 11
20 21 = 3 · 7 70 169 = 120 121 = 170 171 =
21 55 = 5 · 11 71 105 = 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 = 74 75 = 124 125 = 174 175 =
25 28 = 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 29
26 27 = 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59
27 65 = 5 · 13 77 247 = 13 · 19 127 153 = 177 196 =
28 45 = 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 = 80 81 = 130 217 = 7 · 31 180 217 = 7 · 31
31 49 = 81 85 = 5 · 17 131 143 = 11 · 13 181 195 =
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 = 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 = 87 91 = 7 · 13 137 148 = 187 217 = 7 · 31
38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37 188 189 =
39 95 = 5 · 19 89 99 = 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 =
44 45 = 94 95 = 5 · 19 144 145 = 5 · 29 194 195 = 3 · 5 · 13
45 76 = 95 141 = 3 · 47 145 153 = 195 259 = 7 · 37
46 133 = 7 · 19 96 133 = 7 · 19 146 147 = 196 205 = 5 · 41
47 65 = 5 · 13 97 105 = 3 · 5 · 7 147 169 = 197 231 = 3 · 7 · 11
48 49 = 98 99 = 148 231 = 3 · 7 · 11 198 247 = 13 · 19
49 66 = 2 · 3 · 11 99 145 = 5 · 29 149 175 = 199 225 =
50 51 = 3 · 17 100 153 = 150 169 = 200 201 = 3 · 67

参见

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.