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).
