26 1. Arithmetic Functions

x

x

uv x

u

v

Figure 2. Lattice points in the divisor problem

Proof. We have

n≤x

(f ∗ g)(n) =

n≤x km=n

f(k)g(m)

=

k≤y

f(k)

km≤x

g(m) +

ky km≤x

f(k)g(m)

=

k≤y

f(k)G

x

k

+

m≤x/y

g(m)

yk≤x/m

f(k)

=

k≤y

f(k)G

x

k

+

m≤x/y

g(m)⎝

⎛

k≤x/m

f(k) −

k≤y

f(k)⎠

⎞

=

k≤y

f(k)G

x

k

+

m≤x/y

g(m)F

x

m

− F (y)G

x

y

for any y with 1 ≤ y ≤ x.

Questions about divisors more delicate than their gross count have also

been studied. The monograph Divisors by R. R. Hall and G. Tenenbaum is

a good source for information of this kind.