Editing Fermat pseudoprime

{{Short description|Composite number that passes Fermat's probable primality test}}
In [[number theory]], the '''Fermat pseudoprimes''' make up the most important class of [[pseudoprime]]s that come from [[Fermat's little theorem]].

== Definition ==
[[Fermat's little theorem]] states that if <math>p</math> is prime and <math>a</math> is [[coprime]] to <math>p</math>, then <math>a^{p-1}-1</math> is [[Divisor|divisible]] by <math>p</math>. For a positive integer <math>a</math>, if a composite integer <math>x</math> divides <math>a^{x-1}-1</math> then <math>x</math> is called a '''Fermat pseudoprime''' to base <math>a</math>. <ref name="JoyOfFactoring">{{cite book | author = Samuel S. Wagstaff Jr. |author-link = Samuel S. Wagstaff, Jr. | title = The Joy of Factoring | publisher =American Mathematical Society | location = Providence, RI | year = 2013 | isbn = 978-1-4704-1048-3 |url =https://www.ams.org/bookpages/stml-68 }}</ref>{{rp|Def. 3.32}}

In other words, a composite integer is a Fermat pseudoprime to base <math>a</math> if it successfully passes the [[Fermat primality test]] for the base <math>a</math>.<ref name="desmedt-10-23">{{cite book |last=Desmedt |first=Yvo |editor1-last=Atallah |editor1-first=Mikhail J. |editor1-link=Mikhail Atallah |editor2-last=Blanton |editor2-first=Marina |year=2010 |title=Algorithms and theory of computation handbook: Special topics and techniques |chapter=Encryption Schemes |publisher=CRC Press |isbn=978-1-58488-820-8 |pages=10–23 |chapter-url=https://books.google.com/books?id=SbPpg_4ZRGsC&pg=SA10-PA23}}</ref> The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the [[Chinese hypothesis]].

The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: <math>2^{340} \equiv 1 (\bmod{341})</math> and thus passes the
[[Fermat primality test]] for the base 2.

Pseudoprimes to base 2 are sometimes called '''Sarrus numbers''', after [[Pierre Frédéric Sarrus|P. F. Sarrus]] who discovered that 341 has this property, '''Poulet numbers''', after [[Paul Poulet|P. Poulet]] who made a table of such numbers,  or '''Fermatians''' {{OEIS|id=A001567}}.

A Fermat pseudoprime is often called a '''pseudoprime''', with the modifier '''Fermat''' being understood.

An integer <math>x</math> that is a Fermat pseudoprime for all values of <math>a</math> that are coprime to <math>x</math> is called a [[Carmichael number]].<ref name="desmedt-10-23" /><ref name="JoyOfFactoring" />{{rp|Def. 3.34}}

==Properties==

===Distribution===
There are infinitely many pseudoprimes to any given base <math>a > 1</math>. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base <math>a > 1</math>: let <math>A = (a^p-1)/(a-1)</math> and let <math>B = (a^p+1)/(a+1)</math>, where <math>p</math> is a prime number that does not divide <math>a(a^2-1)</math>. Then <math>n= AB</math> is composite, and is a pseudoprime to base <math>a</math>.<ref>{{ cite book | page=108 | author=Paulo Ribenboim |author-link=Paulo Ribenboim | title=The New Book of Prime Number Records | isbn=0-387-94457-5 | publisher=[[Springer-Verlag]] | location=New York | year=1996 }}</ref><ref>{{cite journal | url=https://cs.uwaterloo.ca/journals/JIS/VOL10/Hamahata2/hamahata44.pdf | title=Cipolla Pseudoprimes | last1=Hamahata | first1=Yoshinori | last2=Kokubun | first2=Y. | journal=Journal of Integer Sequences | date=2007 | volume=10| issue=8}}</ref> For example, if <math>a=2</math> and <math>p=5</math>, then <math>A=31</math>, <math>B=11</math>, and <math>n=AB=341</math> is a pseudoprime to base <math>2</math>.

In fact, there are infinitely many [[strong pseudoprime]]s to any base greater than 1 (see Theorem 1 of
<ref name="PSW">{{cite journal |last1=Pomerance |first1=Carl |author-link1=Carl Pomerance |last2=Selfridge |first2=John L. |author-link2=John L. Selfridge |last3=Wagstaff |first3=Samuel S. Jr. |author-link3=Samuel S. Wagstaff Jr. |date=July 1980 |title=The pseudoprimes to 25·10<sup>9</sup> |journal=Mathematics of Computation |doi=10.1090/S0025-5718-1980-0572872-7 |volume=35 |issue=151 |pages=1003–1026 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf |archive-url=https://web.archive.org/web/20050304202721/http://math.dartmouth.edu/~carlp/PDF/paper25.pdf |archive-date=2005-03-04 |url-status=live |doi-access=free }}</ref>) and infinitely many Carmichael numbers,<ref name="Alford1994">{{cite journal |last1=Alford |first1=W. R. |author-link=W. R. (Red) Alford |last2=Granville |first2=Andrew |author-link2=Andrew Granville |last3=Pomerance |first3=Carl |author-link3=Carl Pomerance |year=1994 |title=There are Infinitely Many Carmichael Numbers |journal=[[Annals of Mathematics]] |doi=10.2307/2118576 |volume=140 |issue=3 |pages=703–722 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |archive-url=https://web.archive.org/web/20050304203448/http://math.dartmouth.edu/~carlp/PDF/paper95.pdf |archive-date=2005-03-04 |url-status=live |jstor=2118576 }}</ref> but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·10<sup>9</sup>. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (see Table 1 of <ref name="PSW"/>).

Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all [[Fermat prime|Fermat composites]] and [[Mersenne prime|Mersenne composites]].

The probability of a composite number n passing the Fermat test approaches zero for <math>n \to\infty</math>. Specifically, Kim and Pomerance showed the following: The probability that a random odd number  <math>n \le x</math> is a Fermat pseudoprime to a random base <math>1<b<n-1</math> is less than 2.77·10<sup>−8</sup> for x= 10<sup>100</sup>, and is at most (log x)<sup>−197</sup><10<sup>−10,000</sup> for x≥10<sup>100,000</sup>.<ref>{{cite journal | url=https://www.jstor.org/stable/2008733 | jstor=2008733 | title=The Probability that a Random Probable Prime is Composite | last1=Kim | first1=Su Hee | last2=Pomerance | first2=Carl | journal=Mathematics of Computation | date=1989 | volume=53 | issue=188 | pages=721–741 | doi=10.2307/2008733 }}</ref>

===Factorizations===
The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table.

{{OEIS|id=A001567}}

{| border="0" cellpadding="0" cellspacing="0" 
|- valign="top"
|
{| class="wikitable"
|+ Poulet 1 to 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
|}
|
{| class="wikitable"
|+ Poulet 16 to 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 · 233
|-
|13981||11 · 31 · 41
|-
|14491||43 · 337
|}
|
{| class="wikitable"
|+ Poulet 31 to 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 · 433
|-
|31621||103 · 307
|}
|
{| class="wikitable"
|+ Poulet 46 to 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
|}
|}

A Poulet number all of whose divisors ''d'' divide 2<sup>''d''</sup> − 2 is called a [[super-Poulet number]]. There are infinitely many Poulet numbers which are not super-Poulet Numbers.<ref>{{Citation
|date = 1988-02-15
|edition = 2 Sub
|isbn = 9780444866622
|location = Amsterdam
|publisher = North Holland
|title = Elementary Theory of Numbers
|first = W.
|last = Sierpinski
|chapter = Chapter V.7
|page = 232
|series = North-Holland Mathematical Library
|editor = Ed. A. Schinzel }}</ref>

=== Smallest Fermat pseudoprimes ===
The smallest pseudoprime for each base ''a'' ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below ''a'' are excluded in the table. (For that to allow pseudoprimes below ''a'', see {{oeis|id=A090086}})

{{OEIS|id=A007535}}

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

=== List of Fermat pseudoprimes in fixed base ''n'' ===

{|class="wikitable"
|''n''
|First few Fermat pseudoprimes in base ''n''
|[[OEIS]] sequence
|-
|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)
|{{OEIS link|id=A002808}}
|-
|2
|341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=A020136}}
|-
|5
|4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=A005937}}
|-
|7
|6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=A020142}}
|-
|15
|14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=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, ...
|{{OEIS link|id=A020158}}
|}

For more information (base 31 to 100), see {{oeis|id=A020159}} to {{oeis|id=A020228}}, and for all bases up to 150, see [http://de.m.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Fermatsche_Pseudoprimzahlen table of Fermat pseudoprimes (text in German)], this page does not define ''n'' is a pseudoprime to a base congruent to 1 or −1 (mod ''n'')

==Bases ''b'' for which ''n'' is a Fermat pseudoprime==

If composite <math>n</math> is even, then <math>n</math> is a Fermat pseudoprime to the trivial base <math>b \equiv 1 \pmod n</math>.
If composite <math>n</math> is odd, then <math>n</math> is a Fermat pseudoprime to the trivial bases <math>b \equiv \pm 1 \pmod n</math>.

For any composite <math>n</math>, the ''number'' of distinct bases <math>b</math> modulo <math>n</math>, for which <math>n</math> is a Fermat pseudoprime base <math>b</math>, is
<ref name="lpsp">{{cite journal |author=Robert Baillie |author2=Samuel S. Wagstaff Jr. |author2-link=Samuel S. Wagstaff Jr. |title=Lucas Pseudoprimes|journal=Mathematics of Computation|date=October 1980|volume=35|issue=152|pages=1391–1417|url=http://mpqs.free.fr/LucasPseudoprimes.pdf |archive-url=https://web.archive.org/web/20060906205655/http://mpqs.free.fr/LucasPseudoprimes.pdf |archive-date=2006-09-06 |url-status=live| mr=583518| doi=10.1090/S0025-5718-1980-0583518-6 |doi-access=free}}</ref>{{rp|Thm. 1, p. 1392}}
:<math> \prod_{i=1}^k \gcd(p_i - 1, n - 1)</math>
where <math>p_1, \dots, p_k</math> are the distinct prime factors of <math>n</math>. This includes the trivial bases.

For example, for  <math>n = 341 = 11 \cdot 31</math>, this product is <math>\gcd(10, 340) \cdot \gcd(30, 340) = 100</math>. For <math>n = 341</math>, the smallest such nontrivial base is <math>b = 2</math>.

Every odd composite <math>n</math> is a Fermat pseudoprime to at least two nontrivial bases modulo <math>n</math> unless <math>n</math> is a power of 3.<ref name="lpsp"/>{{rp|Cor. 1, p. 1393}}

For composite ''n'' < 200, the following is a table of all bases ''b'' < ''n'' which ''n'' is a Fermat pseudoprime. If a composite number ''n'' is not in the table (or ''n'' is in the sequence {{OEIS link|id=A209211}}), then ''n'' is a pseudoprime only to the trivial base 1 modulo ''n''.
{|class="wikitable"
|''n''
|bases 0 < ''b'' < ''n'' to which ''n'' is a Fermat pseudoprime
|# of bases<br>{{OEIS2C|id=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
|}

For more information (''n'' = 201 to 5000), see {{lang|de|[[b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999)]]|italic=no}} (Table of pseudoprimes 16–4999).  Unlike the list above, that page excludes the bases 1 and ''n''−1. When ''p'' is a prime, ''p''<sup>2</sup> is a Fermat pseudoprime to base ''b'' [[if and only if]] ''p'' is a [[Wieferich prime]] to base ''b''.  For example, 1093<sup>2</sup> = 1194649 is a Fermat pseudoprime to base 2, and 11<sup>2</sup> = 121 is a Fermat pseudoprime to base 3.

The number of the values of ''b'' for ''n'' are (For ''n'' prime, the number of the values of ''b'' must be ''n'' − 1, since all ''b'' satisfy the [[Fermat little theorem]])
: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, ... {{OEIS|id=A063994}}

The least base ''b'' > 1 which ''n'' is a pseudoprime to base ''b'' (or prime number) are
: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, ... {{OEIS|id=A105222}}

The number of the values of ''b'' for a given ''n'' must divide [[Euler phi function|<math>\varphi</math>]](''n''), or {{OEIS link|id=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 [[if and only if]] ''n'' is a [[Prime number|prime]] or a [[Carmichael number]] (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... {{OEIS link|id=A002997}})  The quotient = 2 if and only if ''n'' is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... {{OEIS link|id=A191311}}.)

The least numbers which are pseudoprime to ''k'' values of ''b'' are (or 0 if no such number exists)
: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, ... {{OEIS|id=A064234}} ([[if and only if]] ''k'' is [[even number|even]] and not [[totient]] of [[squarefree number]], then the ''k''th term of this sequence is 0.)

==Weak pseudoprimes==
A composite number ''n'' which satisfies <math>b^n \equiv b \pmod n</math> is called a '''weak pseudoprime to base ''b'''''.  For any given base ''b'', all Fermat pseudoprimes are weak pseudoprimes, and all weak pseudoprimes coprime to ''b'' are Fermat pseudoprimes.  However, this definition also permits some pseudoprimes which are ''not'' coprime to ''b''.<ref>{{cite web |url=http://www.numericana.com/answer/pseudo.htm#weak |title=Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality |first=Gérard P. |last=Michon |website=Numericana |date=19 November 2003 |access-date=21 April 2018}}</ref>  For example, the smallest even weak pseudoprime to base 2 is 161038 (see {{oeis|id=A006935}}).

The least weak pseudoprime to bases ''b'' = 1, 2, ... are:
: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, ... {{OEIS2C|id=A000790}}

Carmichael numbers are weak pseudoprimes to all bases, thus all terms in this list are less than or equal to the smallest Carmichael number, 561. Except for 561 = 3⋅11⋅17, only [[semiprime]]s can occur in the above sequence. 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|id=A108574}}).  The least Fermat pseudoprime to base ''b'' (also not necessary exceeding ''b'') ({{oeis|A090086}}) is ''usually'' semiprime, but not always; the first counterexample is {{OEIS link|A090086}}(648) = 385 = 5 × 7 × 11.

If we require ''n'' > ''b'', the least weak pseudoprimes (for ''b'' = 1, 2, ...) are:
: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, ... {{OEIS2C|id=A239293}}

== Euler–Jacobi pseudoprimes ==
{{main|Euler–Jacobi pseudoprime}}
Another approach is to use more refined notions of pseudoprimality, e.g. [[strong pseudoprime]]s or [[Euler–Jacobi pseudoprime]]s, for which there are no analogues of [[Carmichael number]]s. This leads to [[randomized algorithm|probabilistic algorithm]]s such as the [[Solovay–Strassen primality test]], the [[Baillie–PSW primality test]], and the [[Miller–Rabin primality test]], which produce what are known as [[industrial-grade primes]]. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure.

==Applications==
The rarity of such pseudoprimes has important practical implications. For example, [[public-key cryptography]] algorithms such as [[RSA (algorithm)|RSA]] require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and [[primality test|test]] them for primality. However, [[deterministic algorithm|deterministic]] primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler [[Fermat primality test]].

==References==
{{Reflist}}

==External links==
*W. F. Galway and Jan Feitsma, [http://www.cecm.sfu.ca/Pseudoprimes/ Tables of pseudoprimes to base 2 and related data] (comprehensive list of all pseudoprimes to base 2 below 2<sup>64</sup>, including factorization, strong pseudoprimes, and Carmichael numbers)
*[http://www.numericana.com/answer/pseudo.htm A research for pseudoprime]

{{Classes of natural numbers}}
{{Pierre de Fermat}}

[[Category:Pseudoprimes]]
[[Category:Asymmetric-key algorithms]]