236 CHAPTER 7 NUMBER THEORY
7.3.6 An Important Counting Principle. Let n = ab, where a ..1 b. Show that if
din then d = uv, where ula and vlb. Moreover, this is a 1-to- 1 correspondence: each
different pair of u, v satisfying ula, vlb produces a different d := uv that divides n.
7.3.7 Use (7.3.6) to conclude that O"(n) is a multiplicative function. For example,
12 = (^3) ·4, with 3 ..14, and we have
0"(12) = 1 +2+4+3+6+ 12
= (1 +2+4)+(1 ·3+2·3+ 4 ·3)
= (1 +2+4)(1 +3)
= 0"(4)0"(3).
7.3.8 Notice in fact, that (7.3.6) can be used to show that O"r(n) is multiplicative, no
matter what r is.
7.3.9 In fact, we can do more. The counting principle that we used can be reformu
lated in the following way: Let n = ab with a ..1 b, and let f be any multiplicative
function. Carefully verify (try several concrete examples) that)J(d) = ) ()J(UV))
din * �� � (�f(U)f(V))
� (�f(U)) (�f(V)).
We have proven the following general fact.Let
F(n) := )f(d).
din
If f is multiplicative then F will be multiplicative as well.Phi and Mu
Define cp (n) to be the number of positive integers less than or equal to n that are
relatively prime to n. For example, cp( 12) = 4, since 1,5,7, II are relatively prime to
12.
We can use PIE (the principle of inclusion-exclusion; see Section 6.3) to evaluate
cp(n). For example, to compute cp(12), the only relevant properties to consider are
divisibility by 2 or divisibility by 3 because 2 and 3 are the only primes that divide 12.
As we have done many times, we shall count the complement; i.e., we will count how