Page 303 - Discrete Mathematics and Its Applications

282 4 / Number Theory and Cryptography

Are there more efficient ways to determine whether an integer is prime? According to some
sources, ancient Chinese mathematicians believed that n was an odd prime if and only if

2 n−1 ≡ 1 (mod n).

If this were true, it would provide an efficient primality test. Why did they believe this
congruence could be used to determine whether an integer n> 2 is prime? First, they observed
that the congruence holds whenever n is an odd prime. For example, 5 is prime and

4
2 5−1 = 2 = 16 ≡ 1 (mod 5).

By Fermat’s little theorem, we know that this observation was correct, that is, 2 n−1 ≡
1 (mod n) whenever n is an odd prime. Second, they never found a composite integer n for
which the congruence holds. However, the ancient Chinese were only partially correct. They
were correct in thinking that the congruence holds whenever n is prime, but they were incorrect
in concluding that n is necessarily prime if the congruence holds.
Unfortunately, there are composite integers n such that 2 n−1 ≡ 1 (mod n). Such integers
are called pseudoprimes to the base 2.

EXAMPLE 10 The integer 341 is a pseudoprime to the base 2 because it is composite (341 = 11 · 31) and as
Exercise 37 shows

2 340 ≡ 1 (mod 341). ▲

We can use an integer other than 2 as the base when we study pseudoprimes.

DEFINITION 1 Let b be a positive integer. If n is a composite positive integer, and b n−1 ≡ 1 (mod n), then
n is called a pseudoprime to the base b.

Given a positive integer n, determining whether 2 n−1 ≡ 1 (mod n) is a useful test that pro-
vides some evidence concerning whether n is prime. In particular, if n satisfies this congruence,
then it is either prime or a pseudoprime to the base 2; if n does not satisfy this congruence, it is
composite. We can perform similar tests using bases b other than 2 and obtain more evidence
as to whether n is prime. If n passes all such tests, it is either prime or a pseudoprime to all the
bases b we have chosen. Furthermore, among the positive integers not exceeding x, where x
is a positive real number, compared to primes there are relatively few pseudoprimes to the
base b, where b is a positive integer. For example, among the positive integers less than 10 10
there are 455,052,512 primes, but only 14,884 pseudoprimes to the base 2. Unfortunately, we

PIERRE DE FERMAT (1601–1665) Pierre de Fermat, one of the most important mathematicians of the
seventeenth century, was a lawyer by profession. He is themostfamous amateurmathematician in history. Fermat
published little of his mathematical discoveries. It is through his correspondence with other mathematicians
that we know of his work. Fermat was one of the inventors of analytic geometry and developed some of
the fundamental ideas of calculus. Fermat, along with Pascal, gave probability theory a mathematical basis.
Fermat formulated what was the most famous unsolved problem in mathematics. He asserted that the equation
n
n
n
x + y = z has no nontrivial positive integer solutions when n is an integer greater than 2. For more than 300
years, no proof (or counterexample) was found. In his copy of the works of the ancient Greek mathematician
Diophantus, Fermat wrote that he had a proof but that it would not fit in the margin. Because the first proof,
found by Andrew Wiles in 1994, relies on sophisticated, modern mathematics, most people think that Fermat thought he had a proof,
but that the proof was incorrect. However, he may have been tempting others to look for a proof, not being able to find one himself.