7.3 NUMBER THEORETIC FUNCTIONS 2357.3 Number Theoretic Functions
Of the infinitely many functions with domain N, we will single out a few that are
especially interesting. Most of these functions are mUltiplicative. A function 1 with
this property satisfies
I(ab) = l(a)/(b)whenever a ..1 b.
7.3. 1 Show that if I: N ---4 N is multiplicative, then 1 (1) = 1.
7.3.2 If a function 1 is multiplicative, then in order to know all values of I, it is
sufficient to know the values of I(pr) for each prime p and each r E N.
Divisor Sums
Definewhere r can be any integer. For example,
0' 2 (10) = 12 +2^2 +5^2 + 10^2 = 130.In other words, O'r(n) is the sum of the rth power of the divisors of n. Although it is
useful to define this function for any value of r, in practice we rarely consider values
other than r = 0 and r = 1.7.3.3 Notice that O'o(n) is equal to the number of divisors of n. This function is usually
denoted by d(n). You encountered it in Example 3.1 on page 68 and Problem 6.1.21
on page 195. Recall that if
n = p�l p�^2 ... p�'
is the prime factorization of n, then
d(n) = (e\ + 1 )(e 2 + 1) ... (et + 1).
From this formula we can conclude that d(n) is a multiplicative function.
7.3.4 Show by examples that d(ab) does not always equal d(a)d(b) if a and b are not
relatively prime. In fact, prove that d(ab) < d(a)d(b) when a and b are not relatively
prime.7.3.5 The function 0'\ (n) is equal to the sum of the divisors of n and is usually denoted
simply by O'(n).
pr+\ _ 1
(a) Show that O'(pr) = for prime p and positive r.
p-1
(b) Show that 0' (pq) = (p + 1) (q + 1) for distinct primes p, q.