The Art and Craft of Problem Solving

7.3. 18 Find n E N such that J.l(n) + J.l(n + I) + J.l(n +
2) = 3.

7.3.19 Show that for all n,r E N,

Gr (n) r

---n

G-r(n) -

.

7.3.20 For n > I, define

ro(n) = � I,

Pm

where the p in the sum must be prime. For n = I, let

ro(n) = 1. In other words, ro(n) is the number of dis­

tinct prime divisors of n. For example, ro( 12) = 2 and

ro(7^3 44) = 1.

(a) Compute ro(n) for n = 1, ... ,25.

(b) What is ro( 17!)?

(c) Is ro multiplicative? Explain.

7.3.21 Likewise, for n > I, define

.Q(n) = �. e,
ptrrn
where again, p must be prime. For n = I, we define
.Q(n) = 1. Thus .Q(n) is the sum of all the exponents
that appear in the prime-power factorization of n. For
example, .Q (12) = 2 + I = 3, because 12 = 2^231 •
(a) Compute.Q(n)forn= 1, ... ,25.
(b) Show, with a counterexample, that .Q is not
multiplicative.
(c) However, there is a simple formula for .Q(ab),
when (a,b) = 1. What is it? Explain.

7.3.22 Define

F(n) = �g(d),

�

where g(l) = I and g(k) = (_1).o(k) if k > 1. Find a

simple rule for the F.

7.3.23 There are two very different ways to prove

7.3.12. One method, which you probably used already,

was to observe that F(n) := }:dln J.l(d) is a multiplica­

tive function, and then calculate that F(pr) = 0 for all

primes. But here is another method: ponder the equa­

tion

1: (ro�n))(_I )k = ( 1_I)oo(n) =0,

where ro(n) was defined in 7.3.20. Explain why this

equation is true, and also why it proves 7.3.12.

7.3 NUMBER THEORETIC FUNCTIONS 239

7.3.24 Prove that tfJ(n) + G(n) = 2n if and only if n is

prime.

7.3.25 Euler's Extension of Fermat's Little Theo­

rem. Emulate the proof of Fermat's little theorem

(page 232) to prove the following:

Let m EN, not necessarily prime, and let

a 1. m. Then

a4'(m) == I (mod m).

7.3.26 Let f(n) be a strictly increasing multiplicative

function with positive integer range satisfying f( I) =

I and f(2) = 2. Prove that f(n) = n for all n.

7.3.27 Find the last two digits of 999 without using a

machine.

The Mobius Inversion Formula

Problems 7.3.28-7. 3.31 explore the Mobius inversion

formula, a remarkable way to "solve" the equation

F(n) = }:dlnf(d) for f·

7.3.28 In 7.3.9, we showed that if F(n) := }:dl" f(d),

and f is mUltiplicative, then F will be multiplicative as

well. Prove the converse of this statement: Show that

if F(n) := }:dlnf(d), and F is multiplicative, then so

f must be multiplicative as well. Suggestion: strong

induction.

7.3.29 Another Counting Principle. Let F(n) :=

}:dlnf(d), and let g be an arbitrary function. Consider

the sum

�g(d)F G) = �g(d) � f(k).

� � klWd)

For each k S n, how many of the terms in this sum will

contain the factor f(k)? First observe that kin. Then

show that the terms containing f(k) will be

Conclude that

f(k) � g(u).

ulWk)

� g(d)F G) = � f(k) � g(u).

� tin ulWk)

The above equations are pretty hairy; but they are not

hard if you get your hands dirty and work out several

examples!