Proof. If F = J f , then

µ F = µ (J f ) = (µ J) f = I f = f,

and conversely, if f = µ F , then

F = F. 2

J f =J (µ F ) = (J µ) F = I

The M¨bius inversion formula says this:

o

F (n) = f (d) for all positive integers n

d|n

if and only if

f (n) = µ(d)F (n/d) for all positive integers n.

d|n

As an application of the M¨bius inversion formula, we can get a di¬erent

o

proof of Theorem 2.14, based on Theorem 2.11. Let F (n) := n and f (n) :=

φ(n). Theorem 2.11 says that F = J f . Applying M¨bius inversion to this

o

yields f = µ F , and using (2.8), we obtain

φ(n) = µ(d)n/d = n µ(d)/d

d|n d|n

= n(1 ’ 1/p1 ) · · · (1 ’ 1/pr ).

Of course, one could turn the above argument around, using M¨bius in-

o

version and (2.8) to derive Theorem 2.11 from Theorem 2.14.

Exercise 2.19. In our de¬nition of a multiplicative function f , we made

the requirement that f (1) = 1. Show that if we dropped this requirement,

the only other function that would satisfy the de¬nition would be the zero

function (i.e., the function that is everywhere zero).

2.6 Arithmetic functions and M¨bius inversion

o 31

Exercise 2.20. Let f be a polynomial with integer coe¬cients, and for

positive integer n de¬ne ωf (n) to be the number of integers z ∈ {0, . . . , n’1}

such that f (z) ≡ 0 (mod n). Show that ωf is multiplicative.

Exercise 2.21. Show that if f and g are multiplicative, then so is f g.

Exercise 2.22. De¬ne „ (n) to be the number of positive divisors of n.

(a) Show that „ is a multiplicative function.

(b) Show that

„ (n) = (e1 + 1) · · · (er + 1),

where n = pe1 · · · per is the prime factorization of n.

r

1

(c) Show that

µ(d)„ (n/d) = 1.

d|n

(d) Show that

µ(d)„ (d) = (’1)r ,

d|n

where n = pe1 · · · per is the prime factorization of n.

r

1

Exercise 2.23. De¬ne σ(n) := d|n d.

(a) Show that σ is a multiplicative function.

(b) Show that

r

pei +1 ’ 1

i

σ(n) = ,

pi ’ 1

i=1

where n = pe1 · · · per is the prime factorization of n.

r

1

(c) Show that

µ(d)σ(n/d) = n.

d|n

(d) Show that

µ(d)σ(d) = (’1)r p1 · · · pr ,

d|n

where n = pe1 · · · per is the prime factorization of n.

r

1

32 Congruences

Exercise 2.24. The Mangoldt function Λ(n) is de¬ned for all positive

integers n by

log p if n = pk , where p is prime and k is a positive integer;

Λ(n) :=

0 otherwise.

(a) Show that

Λ(d) = log n.

d|n

(b) Using part (a), show that

Λ(n) = ’ µ(d) log d.

d|n

Exercise 2.25. Show that if f is multiplicative, and if n = pe1 · · · per is the

r

1

prime factorization of n, then

(µ(d))2 f (d) = (1 + f (p1 )) · · · (1 + f (pr )).

d|n

Exercise 2.26. Show that n is square-free (see Exercise 1.13) if and only if

2

d|n (µ(d)) φ(d) = n.

Exercise 2.27. Show that for any arithmetic function f with f (1) = 0,

there is a unique arithmetic function g, called the Dirichlet inverse of f ,

such that f g = I. Also, show that if f (1) = 0, then f has no Dirichlet

inverse.

Exercise 2.28. Show that if f is a multiplicative function, then so is its

Dirichlet inverse (as de¬ned in the previous exercise).

3

Computing with large integers

In this chapter, we review standard asymptotic notation, introduce the for-

mal computational model we shall use throughout the rest of the text, and

discuss basic algorithms for computing with large integers.

3.1 Asymptotic notation

We review some standard notation for relating the rate of growth of func-

tions. This notation will be useful in discussing the running times of algo-

rithms, and in a number of other contexts as well.

Suppose that x is a variable taking non-negative integer or real values,

and let g denote a real-valued function in x that is positive for all su¬ciently

large x; also, let f denote any real-valued function in x. Then

• f = O(g) means that |f (x)| ¤ cg(x) for some positive constant c and

all su¬ciently large x (read, “f is big-O of g”),

• f = „¦(g) means that f (x) ≥ cg(x) for some positive constant c and

all su¬ciently large x (read, “f is big-Omega of g”),

• f = ˜(g) means that cg(x) ¤ f (x) ¤ dg(x), for some positive con-

stants c and d and all su¬ciently large x (read, “f is big-Theta of

g”),

• f = o(g) means that f /g ’ 0 as x ’ ∞ (read, “f is little-o of g”),

and

• f ∼ g means that f /g ’ 1 as x ’ ∞ (read, “f is asymptotically