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).
Previous Page Next Page