96 6. Integers, Divisors, and Primes
This is a lot of primes! Comparing this with the total number of positive
integers with 200 digits, which we know is 10^200 − 10199 =9· 10199 , we get
9 · 10199
1. 95 · 10197
≈ 460.
Thus among the integers with 200 digits, about one in every 460 is a prime.
(Warning: This argument is not precise; the main source of concern is
that in the Prime Number Theorem we stated only thatπ(n) is close to
n/lnnifnis sufficiently large. One can say more about how largenhas
to be to have, say, an error less than 1 percent, but this leads to even more
difficult questions, which are even today not completely resolved.)
There are many other simple observations one can make by looking at
tables of primes, but they tend to be very difficult, and most of them are not
resolved even today, in some cases after 2,500 years of attempts. We have
already mentioned the problem of twin primes. Another famous unsolved
problem isGoldbach’s conjecture. This states thatevery even integer larger
than 2 can be written as the sum of two primes.Goldbach also formulated
a conjecture about odd numbers:Every odd integer larger than 5 can be
written as the sum of three primes.This second conjecture was essentially
proved, using very deep methods, by Vinogradov in the 1930s. We said
“essentially” since the proof works only for numbers that are very large,
and the possibility of a finite number of exceptions remains open.
Suppose that we have an integernand want to know how soon aftern
we can be sure of finding a prime. For example, how small, or large, is the
first prime with at least 100 digits? Our proof of the infinitude of primes
gives that for everynthere is a prime betweennandn! + 1. This is a very
week statement; it says, for example, that there is a prime between 10 and
10!+1=3, 628 ,801, while of course the next prime is 11. The Russian math-
ematician P.L. Chebyshev proved in the mid-nineteenth century that there
is always a prime betweennand 2n. It has now been proved that there is
always a prime between two consecutive cubes (say, between 10^3 = 1000
and 11^3 = 1331). But it is another old, famous, and still unsolved prob-
lem whether there is always a prime between two consecutive squares. (Try
this out: you’ll in fact find many primes. For example, between 100 = 10^2
and 121 = 11^2 we find 101, 103, 107, 109, 113. Between 100^2 =10, 000
and 101^2 =10,201 we find 10,007, 10,009, 10,037, 10,039, 10,061, 10,067,
10,069, 10,079, 10,091, 10,093, 10,099, 10,103, 10,111, 10,133, 10,139,
10,141, 10,151, 10,159, 10,163, 10,169, 10,177, 10,181, 10,193.)
6.4.1Show that amongk-digit numbers, one in about every 2. 3 kis a prime.