The Art and Craft of Problem Solving

238 CHAPTER 7 NUMBER THEORY

and this makes sense; for we could argue that half of the positive integers up to 360

are odd, and two-thirds of these are not multiples of three, and four-fifths of what are

left are not multiples of five. The final fraction (!. �. �) of 360 will be the numbers

that share no divisors with 360. This argument is not quite rigorous. It tacitly assumes

that divisibility by different primes is in some sense "independent" in a probabilistic

sense. This is true, and it can be made rigorous, but this is not the place for it. 5

Let us pretend to change the subject for a moment by introducing the Mobius

function J1 (n). We define

J1(n) = { �

(-It

if n = 1;

if p^21 n for some prime p;

if n = PIP 2 ··· Pr, each P a distinct prime.

This is a rather bizarre definition, but it turns out that the Mobius function very conve­

niently "encodes" PIE. Here is a table of the first few values of J1(n).

7.3. 11 Verify that J1 is multiplicative.

7.3. 12 Use 7.3.11 and 7.3.9 to show that

tJ1(d) = { 6

if n = 1;

if n > (^1).

The values of J1(n) alternate sign depending on the parity of the number of prime

factors of n. This is what makes the Mobius function related to PIE. For example, we

could rewrite equation (2) as

(3)

This works because of J1 's "filtering" properties. If a divisor d in the sum above con­

tains powers of primes larger than 1, J1 (d) = 0, so the term is not present. If d is equal

to a single prime, say P, the term will be _!!... Likewise, if d = pq, the term becomes

p

+�, etc. And of course (3) is a general formula, true for any n.

pq

Problems and Exercises

7.3.13 Make a table, either by hand or with the aid of

a computer, of the values of den), iP(n), cr(n),J.l(n) for,

say, 1 :S n :S 100 or so.

7.3. 14 Prove that iP(n) = 14 has no solutions.

7.3.15 In 7.3.4, you showed that d(ab) < d(a)d(b)

whenever a and b are relatively prime. What can you

say about the cr function in this case?

7.3. 16 Find the smallest integer n for which iP(n) = 6.

7.3. 17 Find the smallest integer n for which den) =

10.

(^5) See [24] for a wonderful discussion of this and related issues.