费马伪素数
此条目没有列出任何参考或来源。 (2021年11月1日) |
费马伪素数(英语:Fermat pseudoprime)是指满足费马小定理的伪素数,也是最重要的一类伪素数。
其定义是:对自然数和一个与其互素的自然数a,如果整除 ax-1 - 1,则称是一个以a为底的费马伪素数或者关于a的费马伪素数。最小的费马伪素数是341(=11×31,关于2)。如果关于任何与其互素的数都是费马伪素数,则称是绝对伪素数(或卡迈克尔数,来自找到第一个绝对伪素数的数学家罗伯特·丹尼·卡迈克尔)。最小的绝对伪素数是561。
有人已经证明了费马伪素数的个数是无穷的。有一位数学家如此评论:“对于素数,费马小定理肯定是正确的;但他没说在合数中就不正确。”事实上,费马小定理给出的是关于素数判定的必要不充分条件。
另外,若:不是素数(如下表中的情况),则它就一定是伪素数。 这些当中包含了所有的费马合数(当n=2k),梅森合数(当n=p)及瓦格斯塔夫合数(当n=2p)
分圆多项式阶数n | 伪素数 |
11 | 2047=23x89 |
23 | 8388607=47x178481 |
25 | 1082401=601x1801 |
28 | 3277=29x113 |
29 | 536870911=233x1103x2089 |
35 | 8727391=71x122921 |
36 | 4033=37x109 |
37 | 137438953471=223x616318177 |
39 | 9588151=79x121369 |
费马伪素数年表
- 1819年,萨鲁斯(Sarrus)发现第一个伪素数341
- 1903年,马洛(Malo)证明:若n为伪素数,则 也是一个伪素数,从而肯定了伪素数的个数是无穷的。
- 1950年,发现第一个偶伪素数 。
- 1951年,皮格(Beeger)证明了存在无限多个偶伪素数。
以2为底的前50个费马伪素数
n | n | n | n | n | |||||
1 | 341 = | 11 | 2821 = | 21 | 8481 = | 31 | 15709 = 23 · 683 | 41 | 30121 = 7 · 13 · 331 |
2 | 561 = 3 · 11 · 17 | 12 | 3277 = 29 · 113 | 22 | 8911 = 7 · 19 · 67 | 32 | 15841 = 7 · 31 · 73 | 42 | 30889 = 17 · 23 · 79 |
3 | 645 = 3 · 5 · 43 | 13 | 4033 = 37 · 109 | 23 | 10261 = 31 · 331 | 33 | 16705 = 5 · 13 · 257 | 43 | 31417 = 89 · 353 |
4 | 1105 = 5 · 13 · 17 | 14 | 4369 = 17 · 257 | 24 | 10585 = 5 · 29 · 73 | 34 | 18705 = 3 · 5 · 29 · 43 | 44 | 31609 = 73 · 433 |
5 | 1387 = 19 · 73 | 15 | 4371 = 3 · 31 · 47 | 25 | 11305 = 5 · 7 · 17 · 19 | 35 | 18721 = 97 · 193 | 45 | 31621 = 103 · 307 |
6 | 1729 = 7 · 13 · 19 | 16 | 4681 = 31 · 151 | 26 | 12801 = 3 · 17 · 251 | 36 | 19951 = 71 · 281 | 46 | 33153 = 3 · 43 · 257 |
7 | 1905 = 3 · 5 · 127 | 17 | 5461 = 43 · 127 | 27 | 13741 = 7 · 13 · 151 | 37 | 23001 = 3 · 11 · 17 · 41 | 47 | 34945 = 5 · 29 · 241 |
8 | 2047 = 23 · 89 | 18 | 6601 = 7 · 23 · 41 | 28 | 13747 = 59 · 233 | 38 | 23377 = 97 · 241 | 48 | 35333 = 89 · 397 |
9 | 2465 = 5 · 17 · 29 | 19 | 7957 = 73 · 109 | 29 | 13981 = 11 · 31 · 41 | 39 | 25761 = 3 · 31 · 277 | 49 | 39865 = 5 · 7 · 17 · 67 |
10 | 2701 = 37 · 73 | 20 | 8321 = 53 · 157 | 30 | 14491 = 43 · 337 | 40 | 29341 = 13 · 37 · 61 | 50 | 41041 = 7 · 11 · 13 · 41 |
以任意整数为底的最小费马伪素数
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 |