Page 284 - Discrete Mathematics and Its Applications

4.3 Primes and Greatest Common Divisors 263

However, it is possible to prove special cases of Dirichlet’s theorem using the ideas developed
in this book. For example, Exercises 54 and 55 ask for proofs that there are infinitely many
primes in the arithmetic progressions 3k + 2 and 4k + 3, where k is a positive integer. (The hint
for each of these exercises supplies the basic idea needed for the proof.)
We have explained that every arithmetic progression ak + b, k = 1, 2,..., where a and b
have no common factor greater than one, contains infinitely many primes. But are there long
arithmetic progressions made up of just primes? For example, some exploration shows that 5,
11, 17, 23, 29 is an arithmetic progression of five primes and 199, 409, 619, 829, 1039, 1249,
1459, 1669, 1879, 2089 is an arithmetic progression of ten primes. In the 1930s, the famous
mathematician Paul Erd˝os conjectured that for every positive integer n greater than two, there
is an arithmetic progression of length n made up entirely of primes. In 2006, Ben Green and
Terence Tao were able to prove this conjecture. Their proof, considered to be a mathematical
tour de force, is a nonconstructive proof that combines powerful ideas from several advanced
areas of mathematics.

Conjectures and Open Problems About Primes

Number theory is noted as a subject for which it is easy to formulate conjectures, some of which
are difficult to prove and others that remained open problems for many years. We will describe
some conjectures in number theory and discuss their status in Examples 6–9.

EXAMPLE 6 It would be useful to have a function f (n) such that f (n) is prime for all positive integers n.Ifwe
had such a function, we could find large primes for use in cryptography and other applications.
Looking for such a function, we might check out different polynomial functions, as some
mathematicians did several hundred years ago. After a lot of computation we may encounter
2
the polynomial f (n) = n − n + 41. This polynomial has the interesting property that f (n) is
prime for all positive integers n not exceeding 40. [We have f(1) = 41, f(2) = 43, f(3) = 47,
f(4) = 53, and so on.] This can lead us to the conjecture that f (n) is prime for all positive
integers n. Can we settle this conjecture?

Solution: Perhaps not surprisingly, this conjecture turns out to be false; we do not have to look far
2
2
to find a positive integer n for which f (n) is composite, because f(41) = 41 − 41 + 41 = 41 .
2
Because f (n) = n − n + 41 is prime for all positive integers n with 1 ≤ n ≤ 40, we might

TERENCE TAO (BORN 1975) Tao was born in Australia. His father is a pediatrician and his mother taught
mathematics at a Hong Kong secondary school. Tao was a child prodigy, teaching himself arithmetic at the age
of two. At 10, he became the youngest contestant at the International Mathematical Olympiad (IMO); he won
an IMO gold medal at 13. Tao received his bachelors and masters degrees when he was 17, and began graduate
studies at Princeton, receiving his Ph.D. in three years. In 1996 he became a faculty member at UCLA, where
he continues to work.
Tao is extremely versatile; he enjoys working on problems in diverse areas, including harmonic analy-
sis, partial differential equations, number theory, and combinatorics. You can follow his work by reading his
blog where he discusses progress on various problems. His most famous result is the Green-Tao theorem,
which says that there are arbitrarily long arithmetic progressions of primes. Tao has made important contributions to the applications
of mathematics, such as developing a method for reconstructing digital images using the least possible amount of information.
Tao has an amazing reputation among mathematicians; he has become a Mr. Fix-It for researchers in mathematics. The well-known
mathematician Charles Fefferman, himself a child prodigy, has said that “if you’re stuck on a problem, then one way out is to interest
Terence Tao.” In 2006 Tao was awarded a Fields Medal, the most prestigious award for mathematicians under the age of 40. He
was also awarded a MacArthur Fellowship in 2006, and in 2008, he received the Allan T. Waterman award, which came with a
$500,000 cash prize to support research work of scientists early in their career. Tao’s wife Laura is an engineer at the Jet Propulsion
Laboratory.