of numbers, that

C(t) := ci ,

k¤i¤t

and that f (t) has a continuous derivative f (t) on the interval [k, x]. Then

x

ci f (i) = C(x)f (x) ’ C(t)f (t) dt.

k

k¤i¤x

Note that since C(t) is a step function, the integrand C(t)f (t) is piece-

wise continuous on [k, x], and hence the integral is well de¬ned (see §A3).

Proof. Let n := x . We have

n

ci f (i) = C(k)f (k) + [C(k + 1) ’ C(k)]f (k + 1) + · · ·

i=k + [C(n) ’ C(n ’ 1)]f (n)

= C(k)[f (k) ’ f (k + 1)] + · · · + C(n ’ 1)[f (n ’ 1) ’ f (n)]

+ C(n)f (n)

= C(k)[f (k) ’ f (k + 1)] + · · · + C(n ’ 1)[f (n ’ 1) ’ f (n)]

+ C(n)[f (n) ’ f (x)] + C(x)f (x).

Observe that for i = k, . . . , n ’ 1, we have C(t) = C(i) for t ∈ [i, i + 1), and

so

i+1

C(i)[f (i) ’ f (i + 1)] = ’ C(t)f (t) dt;

i

likewise,

x

C(n)[f (n) ’ f (x)] = ’ C(t)f (t) dt,

n

from which the theorem directly follows. 2

5.3 Mertens™ theorem 83

Proof of Theorem 5.10. For i ≥ 2, set

(log i)/i if i is prime,

ci :=

0 otherwise.

By Theorem 5.11, we have

log p

C(t) := ci = = log t + O(1).

p

2¤i¤t p¤t

Applying Theorem 5.12 with f (t) = 1/ log t, we obtain

x

1 C(x) C(t)

= + dt

t(log t)2

p log x 2

p¤x

x x

dt dt

= 1 + O(1/ log x) + + O( )

t(log t)2

t log t

2 2

= 1 + O(1/ log x) + (log log x ’ log log 2) + O(1/ log 2 ’ 1/ log x)

= log log x + O(1). 2

Using Theorem 5.10, we can easily show the following:

Theorem 5.13 (Mertens™ theorem). We have

(1 ’ 1/p) = ˜(1/ log x).

p¤x

Proof. Using parts (i) and (iii) of §A1, for any ¬xed prime p, we have

1 1

’ ¤ + log(1 ’ 1/p) ¤ 0. (5.10)

p2 p

Moreover, since

1 1

¤ < ∞,

p2 i2

p¤x i≥2

summing the inequality (5.10) over all primes p ¤ x yields

1

’C ¤ + log U (x) ¤ 0,

p

p¤x

p¤x (1 ’ 1/p).

where C is a positive constant, and U (x) := From this, and

from Theorem 5.10, we obtain

log log x + log U (x) = O(1).

This means that

’D ¤ log log x + log U (x) ¤ D

84 The distribution of primes

for some positive constant D and all su¬ciently large x, and exponentiating

this yields

e’D ¤ (log x)U (x) ¤ eD ,

and hence, U (x) = ˜(1/ log x), and the theorem follows. 2

Exercise 5.4. Let ω(n) be the number of distinct prime factors of n, and

de¬ne ω(x) = n¤x ω(n), so that ω(x)/x represents the “average” value

of ω. First, show that ω(x) = p¤x x/p . From this, show that ω(x) ∼

x log log x.

∼

Exercise 5.5. Analogously to the previous exercise, show that n¤x „ (n)

x log x, where „ (n) is the number of positive divisors of n.

Exercise 5.6. De¬ne the sequence of numbers n1 , n2 , . . ., where nk is

the product of all the primes up to k. Show that as k ’ ∞, φ(nk ) =

˜(nk / log log nk ). Hint: you will want to use Mertens™ theorem, and also

Theorem 5.6.

Exercise 5.7. The previous exercise showed that φ(n) could be as small

as (about) n/ log log n for in¬nitely many n. Show that this is the “worst

case,” in the sense that φ(n) = „¦(n/ log log n) as n ’ ∞.

Exercise 5.8. Show that for any positive integer constant k,

x

dt x x

= +O .

(log t)k (log x)k (log x)k+1

2

Exercise 5.9. Use Chebyshev™s theorem and Abel™s identity to show that

1 π(x)

+ O(x/(log x)3 ).

=

log p log x

p¤x

Exercise 5.10. Use Chebyshev™s theorem and Abel™s identity to prove a

stronger version of Theorem 5.4:

‘(x) = π(x) log x + O(x/ log x).

Exercise 5.11. Show that

(1 ’ 2/p) = ˜(1/(log x)2 ).

2<p¤x

Exercise 5.12. Show that if π(x) ∼ cx/ log x for some constant c, then we

must have c = 1. Hint: use either Theorem 5.10 or 5.11.

5.4 The sieve of Eratosthenes 85

p¤x 1/p ∼

Exercise 5.13. Strengthen Theorem 5.10, showing that

log log x + A for some constant A. (Note: A ≈ 0.261497212847643.)

p¤x (1 ’

Exercise 5.14. Strengthen Mertens™ theorem, showing that

1/p) ∼ B1 /(log x) for some constant B1 . Hint: use the result from the

previous exercise. (Note: B1 ≈ 0.561459483566885.)

Exercise 5.15. Strengthen the result of Exercise 5.11, showing that

(1 ’ 2/p) ∼ B2 /(log x)2