Snapshot 1: for each

, the graph and tooltip show the number of bases

such that

is a pseudoprime base

Snapshot 2: the number of such bases is usually small compared to

; an exception is

Snapshot 3: for each

, the graph shows the smallest pseudoprime base

(if any) that is greater than 1

If

is prime and

has no factor in common with

, then Fermat's little theorem says that

.

The converse is very often, but not always, true: given

, you choose

at random; if

, then

is very likely to be prime.

The congruence condition

is called a pseudoprime test. If

is composite and

, then

is called a pseudoprime to base

. The only pseudoprimes base 2 that are less than 1000 are 341, 561, and 645: these are the only composite numbers

less than 1000 for which

. In other words, if you designed a primality test that said, "if

then

is prime", then for

, your test would fail only for

,

, and

. Your test would falsely claim that these three numbers are prime.

Although there are three pseudoprimes base 2 less than 1000, pseudoprimes become quite rare. For example, up to

10^{15}, there are only 1,801,533 pseudoprimes base 2 (see [4]), which is about two pseudoprimes per billion integers. So, if

is a large number such that

, then

has a very high probability of being prime.

Pseudoprime tests work so well because if

is composite, there are relatively few values of

for which

. So, if

is composite and you pick base

at random (or always use

), that value of

is unlikely to be a pseudoprime base for

because

is usually some value other than

.

For example, the graph shows that for

, there are just four values of

between 1 and 339 such that

.

By contrast, the graph shows that for

, there are 100 pseudoprime bases between

and

. This is nearly 30% of all possible values of

in this range.

Some bases

are "trivial", that is, useless for primality testing. If

is odd, then

and

always satisfy

, so every odd

always has these two trivial pseudoprime bases. (Also, if

is a power of 3, then

and

are the

*only* such bases; see corollary 1 of theorem 1 in [1].) If

is even, then

is a trivial pseudoprime base for

. So, there are only two nontrivial pseudoprime bases for

, and 98 nontrivial bases for

.

The graph also displays, for each

, the smallest pseudoprime base (if any) that is greater than 1. For

, there are just four pseudoprime bases. There are the two trivial bases,

and

. The smallest nontrivial base is

. The other nontrivial base is

. For

, the smallest nontrivial pseudoprime base is

.

Here is an algorithm to count the number of pseudoprime bases between 1 and

for any given

. First, factor

into primes. Then, for each distinct prime

that divides

, compute

. Finally, multiply these gcd values together. This gives the number of pseudoprime bases for

. For example, suppose

. The number of pseudoprime bases for 341 is

. This algorithm comes from theorem 1 of [1] and from [2].

As noted above, the primality test

fails occasionally, as with

. This test can be made more powerful (i.e. less likely to fail) by combining it with other tests. For example, by Fermat's little theorem, if

is any prime other than 2 or 17, then both congruences

and

are true. But the smallest

*composite* number for which both congruences are true is

. So, for every

, if both of these congruences are true, then

is prime; if at least one of them fails (and

is neither 2 nor 17), then

is composite. In other words, checking both of these congruences gives a primality test that works until

. This extension, and other much more powerful ones, are discussed in [1], [2], [3], and [5].

The exponentiation can be done quickly. For example,

can be computed in only four steps:

,

,

, and

. In

*Mathematica*,

is efficiently computed with

PowerMod[b, n-1, n].

Note: Prime values of

are excluded from the graphs. This is because, if

is prime, the number of pseudoprime bases is

; and this would make the scale on the vertical axis so large that it would be difficult to read the values for composite

.

[2] L. Monier, "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms,"

*Theoretical Computer Science*,

**12**(1), 1980 pp. 97–108.