Multi-Page Printing

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