νp (N ) ¤ log(2m)/ log p, from which it follows that pνp (N ) ¤ 2m.

(5.3) follows immediately from (5.2).

For (5.4), if 2m/3 < p ¤ m, then 2m/p < 3, and we must also have

p ≥ 3, since p = 2 implies m < 3. We have p2 > p(2m/3) = 2m(p/3) ≥ 2m,

and hence all terms with k > 1 in (5.1) vanish. The term with k = 1 also

vanishes, since 1 ¤ m/p < 3/2, from which it follows that 2 ¤ 2m/p < 3,

and hence m/p = 1 and 2m/p = 2.

For (5.5), if m < p < 2m, it follows that 1 < 2m/p < 2, so 2m/p = 1.

Also, m/p < 1, so m/p = 0. It follows that the term with k = 1 in (5.1)

is 1, and it is clear that 2m/pk < 1 for all k > 1, and so all the other terms

vanish. 2

We need one more technical fact, namely, a somewhat better lower bound

on N than that used in the proof of Theorem 5.3:

80 The distribution of primes

2m

Lemma 5.9. Let m ≥ 3 and N = as above. We have

m

m

N > 4 /(2m). (5.6)

Proof. We prove this for all m ≥ 3 by induction on m. One checks by direct

calculation that it holds for m = 3. For m > 3, by induction we have

(2m ’ 1)4m’1

2m ’ 1 2(m ’ 1)

2m

=2 >

m’1 m(m ’ 1)

m m

2m ’ 1 4m 4m

.2

= >

2(m ’ 1) 2m 2m

We now have the necessary technical ingredients to prove Theorem 5.7.

De¬ne

Pm := p,

m<p<2m

and de¬ne Qm so that

N = Qm Pm .

By (5.4) and (5.5), we see that

pνp (N ) .

Qm =

p¤2m/3

√

Moreover, by (5.3), νp (N ) > 1 for at most those p ¤ 2m, so there are at

√

most 2m such primes, and by (5.2), the contribution of each such prime

to the above product is at most 2m. Combining this with Theorem 5.5, we

obtain

√

2m

· 42m/3 .

Qm < (2m)

We now apply (5.6), obtaining

√

N Q’1 ’1

Q’1 ’(1+ 2m)

m m/3

Pm = > 4 (2m) >4 (2m) .

m m

It follows that

√

m log 4

π(2m) ’ π(m) ≥ log Pm / log(2m) > ’ (1 + 2m)

3 log(2m)

√

m(log 4 ’ 1)

m

’ (1 + 2m).

= + (5.7)

3 log(2m) 3 log(2m)

Clearly, the term (m(log 4 ’ 1))/(3 log(2m)) in (5.7) dominates the term

√

1 + 2m, and so Theorem 5.7 holds for all su¬ciently large m. Indeed, a

simple calculation shows that (5.7) implies the theorem for m ≥ 13, 000, and

one can verify by brute force (with the aid of a computer) that the theorem

holds for m < 13, 000.

5.3 Mertens™ theorem 81

5.3 Mertens™ theorem

Our next goal is to prove the following theorem, which turns out to have a

number of applications.

Theorem 5.10. We have

1

= log log x + O(1).

p

p¤x

The proof of this theorem, while not di¬cult, is a bit technical, and we

proceed in several steps.

Theorem 5.11. We have

log p

= log x + O(1).

p

p¤x

Proof. Let n := x . By Theorem 5.2, we have

n/pk log p = n/pk log p.

log(n!) = n/p log p +

p¤n k≥1 p¤n k≥2 p¤n

We next show that the last sum is O(n). We have

p’k

n/pk ¤ n

log p log p

p¤n p¤n

k≥2 k≥2

log p 1 log p

·

=n =n

p2 1 ’ 1/p p(p ’ 1)

p¤n p¤n

log k

¤n = O(n).

k(k ’ 1)

k≥2

Thus, we have shown that

log(n!) = n/p log p + O(n).

p¤n

Further, since n/p = n/p + O(1), applying Theorem 5.5, we have

log p

log(n!) = (n/p) log p + O( log p) + O(n) = n + O(n). (5.8)

p

p¤n p¤n p¤n

We can also estimate log(n!) using a little calculus (see §A2). We have

n n

log t dt + O(log n) = n log n ’ n + O(log n). (5.9)

log(n!) = log k =

1

k=1

82 The distribution of primes

Combining (5.8) and (5.9), and noting that log x ’ log n = o(1), we obtain

log p

= log n + O(1) = log x + O(1),

p

p¤x

which proves the theorem. 2

We shall also need the following theorem, which is a very useful tool in

its own right: