The most important class of pseudoprimes come from the Fermat's little theorem and hence they are called Fermat pseudoprimes. This theorem states that if p is prime and a is coprime to p, then a^{p1}  1 is divisible by p. If a number x is not prime, a is coprime to x and x divides a^{x1}  1, then x is called a pseudoprime to base a. A number x that is a pseudoprime for all values of a that are coprime to x is called a Carmichael number.
The smallest pseudoprime for the base 2 is 341. It is not a prime, since it equals 11 · 31, nevertheless it satisfies Fermats little theorem; 2^{341}=2 (mod 341).
There are applications, such as public key cryptography like RSA that need large prime numbers. The usual algorithm to generate prime numbers is to generate a random odd numbers and test them for primality. However, primality tests are slow. If the user does not require the test to be completely accurate (say, he might tolerate a very small chance that a composite number is declared to be prime), there are fast algorithms based on Fermat's Little Theorem. For example, a simple way to check whether a number x is prime, is to pick some random number a, and check whether x divides a ^{ x }  a. If the answer is no, then x cannot be prime, if the answer is yes, x can be called a "probable prime" and the test can be repeated with other values for a. There's a separate article about the Fermat primality test.
Improved versions of this test give strong probable primes. It has been shown by Monier and Rabin that for the improved test that for each a, the chance of catching a false prime is at least 3 in 4.
There are infinitely many pseudoprimes (in fact infinitely many Carmichael numbers), but they are rather rare. There are only 3 pseudoprimes to base 2 below 1000, to a million there are only 245. Pseudoprimes to base 2 are called Poulet numbers or sometimes Sarrus numbers or Fermatians (SIDN A001567) (http://www.research.att.com/cgibin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001567). Poulet numbers and Carmichael numbers (in bold) below 10000 are:
n  

1  341 = 11 · 31 
2  561 = 3 · 11 · 17 
3  645 = 3 · 5 · 43 
4  1105 = 5 · 13 · 17 
5  1387 = 19 · 73 
6  1729 = 7 · 13 · 19 
7  1905 = 3 · 5 · 127 
8  2047 = 23 · 89 
9  2465 = 5 · 17 · 29 
10  2701 = 37 · 73 
11  2821 = 7 · 13 · 31 
12  3277 = 29 · 112 
13  4033 = 37 · 109 
14  4369 = 17 · 257 
15  4371 = 3 · 31 · 47 
16  4681 = 31 · 151 
17  5461 = 43 · 127 
18  6601 = 7 · 23 · 41 
19  7957 = 73 · 109 
20  8321 = 53 · 157 
21  8481 = 3 · 11 · 257 
22  8911 = 7 · 19 · 67 
A Poulet number all of whose divisors d divide 2^{d}  2 is called superPoulet number. There are an infinitely many Poulet numbers which are not superPoulet Numbers.
The first smallest pseudoprimes for bases a ≤ 200 are given in the following table; the colors mark the number of prime factors.
a  smallest pp  a  smallest pp  a  smallest pp  a  smallest pp 

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

Featured Article
