Page 285 - Discrete Mathematics and Its Applications

264 4 / Number Theory and Cryptography

be tempted to find a different polynomial with the property that f (n) is prime for all positive
integers n. However, there is no such polynomial. It can be shown that for every polynomial
f (n) with integer coefficients, there is a positive integer y such that f(y) is composite. (See
Exercise 23 in the Supplementary Exercises.) ▲

Many famous problems about primes still await ultimate resolution by clever people. We
describe a few of the most accessible and better known of these open problems in Examples 7–9.
Number theory is noted for its wealth of easy-to-understand conjectures that resist attack by all
but the most sophisticated techniques, or simply resist all attacks. We present these conjectures
to show that many questions that seem relatively simple remain unsettled even in the twenty-first
century.
EXAMPLE 7 Goldbach’s Conjecture In 1742, Christian Goldbach, in a letter to Leonhard Euler, conjec-
tured that every odd integer n, n> 5, is the sum of three primes. Euler replied that this conjecture
is equivalent to the conjecture that every even integer n, n> 2, is the sum of two primes (see
Exercise 21 in the Supplementary Exercises). The conjecture that every even integer n, n> 2, is
the sum of two primes is now called Goldbach’s conjecture. We can check this conjecture for
small even numbers. For example, 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 + 3, 12 = 7 + 5,
and so on. Goldbach’s conjecture was verified by hand calculations for numbers up to the mil-
lions prior to the advent of computers. With computers it can be checked for extremely large
numbers. As of mid 2011, the conjecture has been checked for all positive even integers up to
18
1.6 · 10 .
Although no proof of Goldbach’s conjecture has been found, most mathematicians believe
it is true. Several theorems have been proved, using complicated methods from analytic number
theory far beyond the scope of this book, establishing results weaker than Goldbach’s conjecture.
Among these are the result that every even integer greater than 2 is the sum of at most six primes
(proved in 1995 by O. Ramaré) and that every sufficiently large positive integer is the sum of a
prime and a number that is either prime or the product of two primes (proved in 1966 by J. R.
Chen). Perhaps Goldbach’s conjecture will be settled in the not too distant future. ▲

EXAMPLE 8 There are many conjectures asserting that there are infinitely many primes of certain special
forms.A conjecture of this sort is the conjecture that there are infinitely many primes of the form
2
2
2
2
n + 1, where n is a positive integer. For example, 5 = 2 + 1, 17 = 4 + 1, 37 = 6 + 1, and
so on. The best result currently known is that there are infinitely many positive integers n such
2
that n + 1 is prime or the product of at most two primes (proved by Henryk Iwaniec in 1973
using advanced techniques from analytic number theory, far beyond the scope of this book). ▲
EXAMPLE 9 The Twin Prime Conjecture Twin primes are pairs of primes that differ by 2, such as 3 and
5, 5 and 7, 11 and 13, 17 and 19, and 4967 and 4969. The twin prime conjecture asserts that
there are infinitely many twin primes. The strongest result proved concerning twin primes is
that there are infinitely many pairs p and p + 2, where p is prime and p + 2 is prime or the
product of two primes (proved by J. R. Chen in 1966). The world’s record for twin primes, as of
mid 2011, consists of the numbers 65,516,468,355 · 2 333,333 ± 1, which have 100,355 decimal
digits. ▲

CHRISTIAN GOLDBACH (1690–1764) Christian Goldbach was born in Königsberg, Prussia, the city noted for its famous bridge
problem (which will be studied in Section 10.5). He became professor of mathematics at the Academy in St. Petersburg in 1725. In
1728 Goldbach went to Moscow to tutor the son of the Tsar. He entered the world of politics when, in 1742, he became a staff member
in the Russian Ministry of Foreign Affairs. Goldbach is best known for his correspondence with eminent mathematicians, including
Euler and Bernoulli, for his famous conjectures in number theory, and for several contributions to analysis.