Chapter 1

Arithmetic Functions

1.1. The method of Chebyshev

Around 1792 J. K. F. Gauss counted primes in successive blocks of a thou-

sand integers, and noticed that the sequence of primes seems to thin out

according to a definite law. One formulation of his law is that the intervals

(x − h, x] contain about h/ log(x) primes when x is large and h is not too

small. Another way to express the same empirical observation is that the

chance of a randomly chosen large integer n being prime is approximately

1/ log(n). Gauss went on to integrate this density to obtain the approxima-

tion

π(x)

def

=

p≤x

1 ≈ li(x)

def

=

x

2

du

log(u)

for the counting function π(x) of the primes. Here li(x) is the integral loga-

rithm. By his counts of primes, Gauss guessed that limx→+∞ π(x)/li(x) = 1.

This is simply the statement that the relative error |π(x) − li(x)|/π(x) in

the approximation goes to zero as x → +∞. Using the notation

f(x) ∼ g(x)

def

⇐⇒ lim

x→+∞

f(x)

g(x)

= 1

of asymptotic equality familiar from analysis, the conjecture can be ex-

pressed as π(x) ∼ li(x). This is the Prime Number Theorem (abbreviated

PNT) first proved by J. S. Hadamard and C. G. J. N. de la Vall´ ee Poussin

in 1896. Since li(x) ∼ x/ log(x) by l’Hˆ opital’s rule, the PNT also has the

formulation π(x) ∼ x/ log(x), showing that about 1/ log(x) of the positive

integers up to x are prime.

Because the density of the primes near n is approximately 1/ log(n), it

may be more natural to count each prime p with weight log(p) rather than

1