2 1. Arithmetic Functions

with weight 1. This gives the weighted counting function

ϑ(x)

def

=

p≤x

log(p)

introduced by P. L. Chebyshev. To obtain nice formulas that are easier to

analyze, it is advantageous also to count prime powers

pk

with weight log(p).

The von Mangoldt function Λ given by

Λ(pk)

= log(p) when the argument

is a prime power, and zero otherwise, serves this purpose. The weighted

counting function

ψ(x)

def

=

pk≤x

log(p) =

n≤x

Λ(n)

was also introduced by Chebyshev. Since prime powers with exponent higher

than one are quite sparse, ψ(x) mainly counts primes with weight log(p).

The functions ψ(x) and ϑ(x) are thus approximately equal, and both are

closely related to the counting function π(x) of the primes. In particular it

will turn out that the Prime Number Theorem may equally well be expressed

as one of the asymptotic relations ψ(x) ∼ x or ϑ(x) ∼ x. These formulations

are often more convenient.

The integers n = pm in the interval 0 n ≤ N that are divisible by

a prescribed prime p are given by the integer solutions m of the inequality

0 m ≤ N/p. The largest integer less than or equal to a real number x is

denoted by [x]. It is called the integer part of x or the Gauss bracket. Clearly

[N/p] is the number of integers n as above. The same reasoning shows that,

of these integers, exactly

[N/pk]

are divisible by

pk.

This observation allows

us to write down the prime factorization

N! =

pk

p[N/pk]

of the factorial, due to A.-M. Legendre. The product is taken over all prime

powers, but has only finitely many factors different from 1 because

[N/pk]

=

0 when

pk

N. The importance of the identity lies in the fact that the left-

hand side does not contain the primes explicitly, and is susceptible of being

estimated analytically. Taking the logarithm on both sides of the Legendre

identity yields

n≤N

Λ(n)

N

n

=

pk

log(p)

N

pk

= log(N!).

Now

pk

log(p)

N

pk

=

pk

log(p)

mpk≤N

1 =

m≤N

pk≤N/m

log(p)