查看“︁费马伪素数”︁的源代码

{{Unreferenced|time=2021-11-01T00:22:51+00:00}}
{{TA|G1=Math}}
'''费马伪素数'''（{{lang-en|Fermat pseudoprime}}）是指满足[[费马小定理]]的[[伪素数]]，也是最重要的一类伪素数。

其定义是：对[[自然数]]<math>x</math>和一个与其互素的自然数''a''，如果<math>x</math>整除 ''a''<sup>''x''-1</sup> - 1，则称<math>x</math>是一个以''a''为底的费马伪素数或者关于''a''的费马伪素数。最小的费马伪素数是[[341]]（''=11×31''，关于2）。如果<math>x</math>关于任何与其互素的数都是费马伪素数，则称<math>x</math>是[[绝对伪素数]]（或[[卡邁克爾數]]，来自找到第一个绝对伪素数的数学家羅伯特·丹尼·卡邁克爾）。最小的绝对伪素数是[[561]]。

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

另外，若:<math>\frac{\Phi_n(2)}{\gcd(\Phi_n(2),n)}</math>不是質數（如下表中的情況），則它就一定是偽質數。
這些當中包含了所有的[[費馬質數|費馬合數]]（當n=2<sup>k</sup>），[[梅森質數|梅森合數]](當n=p)及[[瓦格斯塔夫質數|瓦格斯塔夫合數]]（當n=2p）

{| class="wikitable"
|分圓多項式階數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为伪素数，则<math>m=2^n-1</math>也是一个伪素数，从而肯定了伪素数的个数是无穷的。
* 1950年，发现第一个偶伪素数 <math>161038=2 \times 73 \times 1103</math>。
* 1951年，[[皮格]]（Beeger）证明了存在无限多个偶伪素数。

== 以2为底的前50个费马伪素数 ==
{{OEIS|id=A001567}}
{| class="wikitable"
|n || ||n || ||n || ||n || ||n ||
|-
|1 ||341 = {{質因數分解|341}} ||11 ||'''2821''' = {{質因數分解|2821}} ||21 ||8481 = {{質因數分解|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
|}

== 以任意整数为底的最小费马伪素数 ==
{{OEIS|id=A007535}}
{| class="wikitable"
|-
! ''a''
! 最小的伪素数
! ''a''
! 最小的伪素数
! ''a''
! 最小的伪素数
! ''a''
! 最小的伪素数
|-
| bgcolor="#FFCBCB" | 1
| bgcolor="#FFCBCB" | 4 = {{質因數分解|4}}
| 51
| 65 = 5 · 13
| bgcolor="#FFEBAD" | 101
| bgcolor="#FFEBAD" | 175 = {{質因數分解|175}}
| bgcolor="#FFEBAD" | 151
| bgcolor="#FFEBAD" | 175 = {{質因數分解|175}}
|-
| 2
| 341 = 11 · 31
| 52
| 85 = 5 · 17
| 102
| 133 = 7 · 19
| bgcolor="#FFEBAD" | 152
| bgcolor="#FFEBAD" | 153 = {{質因數分解|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
| bgcolor="#B3B7FF" | 104
| bgcolor="#B3B7FF" | 105 = 3 · 5 · 7
| 154
| 155 = 5 · 31
|-
| bgcolor="#FFEBAD" | 5
| bgcolor="#FFEBAD" | 124 = {{質因數分解|124}}
| bgcolor="#FFEBAD" | 55
| bgcolor="#FFEBAD" | 63 = {{質因數分解|63}}
| 105
| 451 = 11 · 41
| bgcolor="#B3B7FF" | 155
| bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
|-
| 6
| 35 = 5 · 7
| 56
| 57 = 3 · 19
| 106
| 133 = 7 · 19
| 156
| 217 = 7 · 31
|-
| bgcolor="#FFCBCB" | 7
| bgcolor="#FFCBCB" | 25 = {{質因數分解|25}}
| 57
| 65 = 5 · 13
| 107
| 133 = 7 · 19
| bgcolor="#B3B7FF" | 157
| bgcolor="#B3B7FF" | 186 = 2 · 3 · 31
|-
| bgcolor="#FFCBCB" | 8
| bgcolor="#FFCBCB" | 9 = {{質因數分解|9}}
| 58
| 133 = 7 · 19
| 108
| 341 = 11 · 31
| 158
| 159 = 3 · 53
|-
| bgcolor="#FFEBAD" | 9
| bgcolor="#FFEBAD" | 28 = {{質因數分解|28}}
| 59
| 87 = 3 · 29
| bgcolor="#FFEBAD" | 109
| bgcolor="#FFEBAD" | 117 = {{質因數分解|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
| bgcolor="#B3B7FF" | 111
| bgcolor="#B3B7FF" | 190 = 2 · 5 · 19
| bgcolor="#B3B7FF" | 161
| bgcolor="#B3B7FF" | 190 = 2 · 5 · 19
|-
| 12
| 65 = 5 · 13
| bgcolor="#FFEBAD" | 62
| bgcolor="#FFEBAD" | 63 = {{質因數分解|63}}
| bgcolor="#FFCBCB" | 112
| bgcolor="#FFCBCB" | 121 = {{質因數分解|121}}
| 162
| 481 = 13 · 37
|-
| 13
| 21 = 3 · 7
| 63
| 341 = 11 · 31
| 113
| 133 = 7 · 19
| bgcolor="#B3B7FF" | 163
| bgcolor="#B3B7FF" | 186 = {{質因數分解|186}}
|-
| 14
| 15 = 3 · 5
| 64
| 65 = 5 · 13
| 114
| 115 = 5 · 23
| bgcolor="#B3B7FF" | 164
| bgcolor="#B3B7FF" | 165 = {{質因數分解|165}}
|-
| 15
| 341 = 11 · 31
| bgcolor="#FFEBAD" | 65
| bgcolor="#FFEBAD" | 112 = {{質因數分解|112}}
| 115
| 133 = 7 · 19
| bgcolor="#FFEBAD" | 165
| bgcolor="#FFEBAD" | 172 = {{質因數分解|172}}
|-
| 16
| 51 = 3 · 17
| 66
| 91 = 7 · 13
| bgcolor="#FFEBAD" | 116
| bgcolor="#FFEBAD" | 117 = {{質因數分解|117}}
| 166
| 301 = 7 · 43
|-
| bgcolor="#FFEBAD" | 17
| bgcolor="#FFEBAD" | 45 = {{質因數分解|45}}
| 67
| 85 = 5 · 17
| 117
| 145 = 5 · 29
| bgcolor="#B3B7FF" | 167
| bgcolor="#B3B7FF" | 231 = {{質因數分解|231}}
|-
| bgcolor="#FFCBCB" | 18
| bgcolor="#FFCBCB" | 25 = {{質因數分解|25}}
| 68
| 69 = 3 · 23
| 118
| 119 = 7 · 17
| bgcolor="#FFCBCB" | 168
| bgcolor="#FFCBCB" | 169 = {{質因數分解|169}}
|-
| bgcolor="#FFEBAD" | 19
| bgcolor="#FFEBAD" | 45 = {{質因數分解|45}}
| 69
| 85 = 5 · 17
| 119
| 177 = 3 · 59
| bgcolor="#B3B7FF" | 169
| bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
|-
| 20
| 21 = 3 · 7
| bgcolor="#FFCBCB" | 70
| bgcolor="#FFCBCB" | 169 = {{質因數分解|169}}
| bgcolor="#FFCBCB" | 120
| bgcolor="#FFCBCB" | 121 = {{質因數分解|121}}
| bgcolor="#FFEBAD" | 170
| bgcolor="#FFEBAD" | 171 = {{質因數分解|171}}
|-
| 21
| 55 = 5 · 11
| bgcolor="#B3B7FF" | 71
| bgcolor="#B3B7FF" | 105 = {{質因數分解|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
|-
| bgcolor="#FFCBCB" | 24
| bgcolor="#FFCBCB" | 25 = {{質因數分解|25}}
| bgcolor="#FFEBAD" | 74
| bgcolor="#FFEBAD" | 75 = {{質因數分解|75}}
| bgcolor="#FFEBAD" | 124
| bgcolor="#FFEBAD" | 125 = {{質因數分解|125}}
| bgcolor="#FFEBAD" | 174
| bgcolor="#FFEBAD" | 175 = {{質因數分解|175}}
|-
| bgcolor="#FFEBAD" | 25
| bgcolor="#FFEBAD" | 28 = {{質因數分解|28}}
| 75
| 91 = 7 · 13
| 125
| 133 = 7 · 19
| 175
| 319 = 11 · 29
|-
| bgcolor="#FFEBAD" | 26
| bgcolor="#FFEBAD" | 27 = {{質因數分解|27}}
| 76
| 77 = 7 · 11
| 126
| 247 = 13 · 19
| 176
| 177 = 3 · 59
|-
| 27
| 65 = 5 · 13
| 77
| 247 = 13 · 19
| bgcolor="#FFEBAD" | 127
| bgcolor="#FFEBAD" | 153 = {{質因數分解|153}}
| bgcolor="#FFEBAD" | 177
| bgcolor="#FFEBAD" | 196 = {{質因數分解|196}}
|-
| bgcolor="#FFEBAD" | 28
| bgcolor="#FFEBAD" | 45 = {{質因數分解|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
|-
| bgcolor="#FFCBCB" | 30
| bgcolor="#FFCBCB" | 49 = {{質因數分解|49}}
| bgcolor="#FFEBAD" | 80
| bgcolor="#FFEBAD" | 81 = {{質因數分解|81}}
| 130
| 217 = 7 · 31
| 180
| 217 = 7 · 31
|-
| bgcolor="#FFCBCB" | 31
| bgcolor="#FFCBCB" | 49 = {{質因數分解|49}}
| 81 
| 85 = 5 · 17
| 131
| 143 = 11 · 13
| bgcolor="#B3B7FF" | 181
| bgcolor="#B3B7FF" | 195 = {{質因數分解|195}}
|-
| 32
| 33 = 3 · 11
| 82
| 91 = 7 · 13
| 132
| 133 = 7 · 19
| 182
| 183 = 3 · 61
|-
| 33
| 85 = 5 · 17
| bgcolor="#B3B7FF" | 83
| bgcolor="#B3B7FF" | 105 = 3 · 5 · 7
| 133
| 145 = 5 · 29
| 183
| 221 = 13 · 17
|-
| 34
| 35 = 5 · 7
| 84
| 85 = 5 · 17
| bgcolor="#FFEBAD" | 134
| bgcolor="#FFEBAD" | 135 = {{質因數分解|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
|-
| bgcolor="#FFEBAD" | 37
| bgcolor="#FFEBAD" | 45 = {{質因數分解|45}}
| 87
| 91 = 7 · 13
| bgcolor="#FFEBAD" | 137
| bgcolor="#FFEBAD" | 148 = {{質因數分解|148}}
| 187
| 217 = 7 · 31
|-
| 38
| 39 = 3 · 13
| 88
| 91 = 7 · 13
| 138
| 259 = 7 · 37
| bgcolor="#FFEBAD" | 188
| bgcolor="#FFEBAD" | 189 = {{質因數分解|189}}
|-
| 39
| 95 = 5 · 19
| bgcolor="#FFEBAD" | 89
| bgcolor="#FFEBAD" | 99 = {{質因數分解|99}}
| 139
| 161 = 7 · 23
| 189
| 235 = 5 · 47
|-
| 40
| 91 = 7 · 13
| 90
| 91 = 7 · 13
| 140
| 141 = 3 · 47
| bgcolor="#B3B7FF" | 190
| bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
|-
| bgcolor="#B3B7FF" | 41
| bgcolor="#B3B7FF" | 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
| bgcolor="#FFEBAD" | 193
| bgcolor="#FFEBAD" | 276 = {{質因數分解|276}}
|-
| bgcolor="#FFEBAD" | 44
| bgcolor="#FFEBAD" | 45 = {{質因數分解|45}}
| 94
| 95 = 5 · 19
| 144
| 145 = 5 · 29
| bgcolor="#B3B7FF" | 194
| bgcolor="#B3B7FF" | 195 = 3 · 5 · 13
|-
| bgcolor="#FFEBAD" | 45
| bgcolor="#FFEBAD" | 76 = {{質因數分解|76}}
| 95
| 141 = 3 · 47
| bgcolor="#FFEBAD" | 145
| bgcolor="#FFEBAD" | 153 = {{質因數分解|153}}
| 195
| 259 = 7 · 37
|-
| 46
| 133 = 7 · 19
| 96
| 133 = 7 · 19
| bgcolor="#FFEBAD" | 146
| bgcolor="#FFEBAD" | 147 = {{質因數分解|147}}
| 196
| 205 = 5 · 41
|-
| 47
| 65 = 5 · 13
| bgcolor="#B3B7FF" | 97
| bgcolor="#B3B7FF" | 105 = 3 · 5 · 7
| bgcolor="#FFCBCB" | 147
| bgcolor="#FFCBCB" | 169 = {{質因數分解|169}}
| bgcolor="#B3B7FF" | 197
| bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
|-
| bgcolor="#FFCBCB" | 48
| bgcolor="#FFCBCB" | 49 = {{質因數分解|49}}
| bgcolor="#FFEBAD" | 98
| bgcolor="#FFEBAD" | 99 = {{質因數分解|99}}
| bgcolor="#B3B7FF" | 148
| bgcolor="#B3B7FF" | 231 = 3 · 7 · 11
| 198
| 247 = 13 · 19
|-
| bgcolor="#B3B7FF" | 49
| bgcolor="#B3B7FF" | 66 = 2 · 3 · 11
| 99
| 145 = 5 · 29
| bgcolor="#FFEBAD" | 149
| bgcolor="#FFEBAD" | 175 = {{質因數分解|175}}
| bgcolor="#FFEBAD" | 199
| bgcolor="#FFEBAD" | 225 = {{質因數分解|225}}
|-
| 50
| 51 = 3 · 17
| bgcolor="#FFEBAD" | 100
| bgcolor="#FFEBAD" | 153 = {{質因數分解|153}}
| bgcolor="#FFCBCB" | 150
| bgcolor="#FFCBCB" | 169 = {{質因數分解|169}}
| 200
| 201 = 3 · 67
|}

== 参见 ==
* [[卡迈克尔数]]
* [[欧拉伪素数]]
* [[欧拉－雅可比伪素数]]

{{質數}}
{{皮埃爾·德·費馬}}

[[Category:伪素数]]