Number Theory: An Introduction to Mathematics

368 IX The Number of Prime Numbers

Proof Since

ψ(x)=

∑

p≤x

logp+

∑

p^2 ≤x

logp+···

andk>logx/log 2 impliesx^1 /k<2, we have

ψ(x)=θ(x)+θ(x^1 /^2 )+···+θ(x^1 /m),

wherem =logx/log 2. (As is now usual, we denote byythe greatest integer
≤y.) But it is obvious from the definition ofθ(x)thatθ(x)=O(xlogx). Hence

ψ(x)−θ(x)=O

(∑

2 ≤k≤m

x^1 /klogx

)

=O(x^1 /^2 log^2 x).

Ifθ(x)=O(x)the same argument yieldsψ(x)−θ(x)=O(x^1 /^2 logx)and thus
ψ(x)=O(x). It is trivial thatψ(x)=O(x)impliesθ(x)=O(x).

The proof of Lemma 3 shows also that

ψ(x)=θ(x)+θ(x^1 /^2 )+O(x^1 /^3 log^2 x).

Lemma 4ψ(x)=O(x)if and only ifπ(x)=O(x/logx), and then

π(x)logx/x=ψ(x)/x+O( 1 /logx).

Proof Although their use can easily be avoided, it is more suggestive to use Stieltjes
integrals. Suppose first thatψ(x)=O(x).Foranyx>2wehave

π(x)=

∫x+

2 −

1 /logtdθ(t)

and hence, on integrating by parts,

π(x)=θ(x)/logx+

∫x

2

θ(t)/tlog^2 tdt.

But
∫x

2

θ(t)/tlog^2 tdt=O(x/log^2 x),

sinceθ(t)=O(t)and, as we saw in§1,

∫x

2

dt/log^2 t=O(x/log^2 x).

Since

θ(x)/logx=ψ(x)/logx+O(x^1 /^2 ),