6.10 How to Test Whether a Number is a Prime? 119Unfortunately, the answer is yes. The smallest such number is 341 = 11·31.
This is not a prime, but it satisfies
341 | 2340 − 1. (6.8)(How do we know that this divisibility relation holds without extensive
computation? We can use Fermat’s Theorem. It is sufficient to argue that
both 11 and 31 are divisors of 2^340 −1, since then so is their product, 11
and 31 being different primes. By Fermat’s Theorem,
11 | 210 − 1.Next we invoke the result of Exercise 6.1.6: It implies that
210 − 1 | 2340 − 1.Hence
11 | 2340 − 1.
For 31, we don’t need Fermat’s Theorem, but only exercise (6.1.6) again:
31 = 2^5 − 1 | 2340 − 1.This proves (6.8).)
Such numbers, which are not primes but behave like primes in the sense
that Fermat’s Theorem with basea= 3 holds true for them, are called
pseudoprimes(fake primes), or more precisely, pseudoprimes to base 2.
While such numbers are quite rare (there are only 22 pseudoprimes to base
2 between 1 and 10,000), they do show that our primality test can give
a “false positive,” and thus (in a strict mathematical sense) it is not a
primality test at all.
(If we can afford to make an error every now and then, then we can
live with the simple Fermat test with base 2. If the worst that can happen
when a composite number is believed to be a prime is that a computer game
crashes, we can risk this; if the security of a bank, or a country, depends
on not using a fake prime, we have to find something better.)
One idea that comes to the rescue is that we haven’t used the full force
of Fermat’s Theorem: We can also check thatn| 3 n−3,n| 5 n−5, etc.
These tests can be carried out using the same tricks as described above.
And in fact, already the first of these tests rules out the “fake prime” 341:
it is not a divisor of 3^340 −1.
The following observation tells us that this always works, at least if we
are patient enough:
A positive integern> 1 is a prime if and only if it passes the
Fermat test
n|an−^1 − 1
for every basea=1, 2 , 3 ,...,n− 1.