38 1. Arithmetic Functions

(44) An arithmetic function h is given, which is never zero. It is known that

h = fg where f is multiplicative and g is additive. Determine f and g

from h.

(45) a) The sieve of Eratosthenes-Legendre: Show that

d|P

μ(d)

x

d

= π(x) − π(

√

x) + 1

if P√x denotes the product of the primes p ≤

√

x.

b) Show that

π(x) ≤ π(z) − 1 +

d|Pz

μ(d)

x

d

if Pz denotes the product of the primes p ≤ z.

c) Show that π(x) x/ log log(x) by a choice of z in terms of x in part

b). This is weaker than what we already have from Section 1.1, but see

the next part.

d) In the sieve of Eratosthenes-Legendre, we calculated the number of

primes in the interval

√

x n ≤ x by removing those integers that lie

in arithmetic progressions pZ with p ≤

√

x. Apply the same idea on

the interval x − h n ≤ x to show that a bound π(x) − π(x − h)

h/ log log(h) holds uniformly in x. Does this follow from the Chebyshev

theory of Section 1.1?

(46) Find a maximal order and a minimal order of log(φ(n)).

(47) Use the Dirichlet interchange to show that 1 ∗ λ = , where is the

characteristic function of the squares.

(48) Use the Dirichlet interchange to calculate 1 ∗ log.

(49) A natural number n is called perfect if σ(n) = 2n. Use the Dirichlet

interchange and congruences modulo 3 to show that n ≡ 2 (mod 3) if n

is perfect (J. Touchard).

(50) Find the arithmetic average of the fractional part {x/n} = x/n − [x/n]

of x/n over the interval 1 ≤ n ≤ x as x → +∞ (Dirichlet).

(51) Show that for every ε 0 the equation xu − yv = 1 has

Oε(R2+ε)

solutions in integers in the ball

x2

+

y2

+

u2

+

v2

≤

R2.

(52) a) Show that

n≤x

f(n)G

x

n

=

m≤x

(G(m) − G(m − 1))F

x

m

if f(n) is an arithmetic function with summatory function F (x) and

G(x) is the summatory function of some arithmetic function (Dirichlet).