Editing Fermat pseudoprime (section)

==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.)