Number Theory: An Introduction to Mathematics

1 Finding the Problem 365

where lognx =(logx)n. By repeatedly integrating by parts it may be seen that, for
each positive integern,

∫x

2

dt/logt={ 1 +1!/logx+2!/log^2 x+···+(n− 1 )!/logn−^1 x}x/logx

+n!

∫x

2

dt/logn+^1 t+cn,

wherecnis a constant. Moreover, using theLandau order symboldefined under
‘Notations’,
∫x

2

dt/logn+^1 t=O(x/logn+^1 x),

since

∫x 1 / 2

2

dt/logn+^1 t<x^1 /^2 /logn+^12 ,

∫x

x^1 /^2

dt/logn+^1 t< 2 n+^1 x/logn+^1 x.

Thus Chebyshev’s result shows thatA=B =1 are the best possible values for a
formula of Legendre’s type and suggests that

Li(x)=

∫x

2

dt/logt

is a better approximation toπ(x).
If we interpret this approximation as an asymptotic formula, then it implies that
π(x)logx/x→1asx→∞, i.e., using anotherLandau order symbol,

π(x)∼x/logx. (1)

The validity of the relation (1) is now known as theprime number theorem.Ifthen-th
prime is denoted bypn, then the prime number theorem can also be stated in the form
pn∼nlogn:

Proposition 2π(x)∼x/logx if and only if pn∼nlogn.

Proof Ifπ(x)logx/x→1, then

logπ(x)+log logx−logx→ 0

and hence

logπ(x)/logx→ 1.

Consequently

π(x)logπ(x)/x=π(x)logx/x·logπ(x)/logx→ 1.

Sinceπ(pn)=n, this shows thatpn∼nlogn.