120 6. Integers, Divisors, and Primes
Fermat’s Theorem tells us that primes do pass the Fermat test for every
base. On the other hand, ifnis composite, then there are numbersa,
1 ≤a≤n−1, that are not relatively prime ton, and every suchawill fail
the Fermat test: Indeed, ifpis a common prime divisor ofaandn, then
pis a divisor ofan−^1 , so it cannot be a divisor ofan−^1 −1, and hencen
cannot be a divisor ofan−^1 −1.
But this general Fermat test is not efficient enough. Imagine that we
are given a natural numbern, with a few hundred digits, and we want to
test whether or not it is a prime. We can carry out the Fermat test with
base 2. Suppose it passes. Then we can try base 3. Suppose it passes again,
etc. How long do we have to go before we can conclude thatnis a prime?
Looking at the argument above justifying the general Fermat test, we see
that we don’t have to go farther than the first number having a common
divisor withn. It is easy to see that the smallest such number is the least
prime divisor ofn. For example, ifn=pq, wherepandqare distinct
primes, having say 100 digits each (sonhas 199 or 200 digits), then we
have to try everything up to the smaller ofpandq, which is more than
1099 trials, which is hopelessly large. (And furthermore, if we go this far
anyway, we may do a simple divisibility test, no need for anything fancy
like Fermat’s Theorem!)
Instead of starting with 2, we could start checking whether Fermat’s
Theorem holds with any other basea; for example, we could choose a
random integerain the range 1≤a≤n−1. We know that it fails if we hit
anyathat is not relatively prime ton. Does this give us a good chance of
discovering thatnis not a prime if in fact it is not? This depends onn, but
certain values ofnare definitely bad. For example, suppose thatn=pq
wherepandqare different primes. It is easy to list those numbersathat are
not relatively prime ton: these are the multiples ofp(p, 2 p,...,(q−1)p, qp)
and the multiples ofq(q, 2 q,...,(p−1)q, pq). The total number of such
numbersaisq+p−1 (sincepq=noccurs on both lists). This number is
larger than 2· 1099 , but less than 2· 10100 , and so the probability that we
hit one of these number when we choose a randomais less than
2 · 10100
10199
=2· 10 −^99 ,
which shows that this event has way too small a probability to ever happen
in practice.
Carmichael numbers.Our next hope is that perhaps for a composite
numbern, the Fermat test will fail much earlier than its smallest prime
divisor, or else for a random choice ofait will fail for many other numbers
besides those not relatively prime ton. Unfortunately, this is not always
so. There are integersn, calledCarmichael numbers, which are even worse
than pseudoprimes: They pass the Fermat test for every basearelatively