side of (2.6), we obtain

±φ(n) = [1]n .

That proves the ¬rst statement of the theorem. The second follows from

the observation made above that ±i = [1]n if and only if the multiplicative

order of ± divides i. 2

As a consequence of this, we obtain:

Theorem 2.16 (Fermat™s little theorem). For any prime p, and any

integer a ≡ 0 (mod p), we have ap’1 ≡ 1 (mod p). Moreover, for any

integer a, we have ap ≡ a (mod p).

Proof. The ¬rst statement follows from Theorem 2.15, and the fact that

φ(p) = p ’ 1. The second statement is clearly true if a ≡ 0 (mod p),

and if a ≡ 0 (mod p), we simply multiply both sides of the congruence

ap’1 ≡ 1 (mod p) by a. 2

For a positive integer n, we say that a ∈ Z with gcd(a, n) = 1 is a

primitive root modulo n if the multiplicative order of a modulo n is

equal to φ(n). If this is the case, then for ± := [a]n , the powers ±i range

over all elements of Z— as i ranges over the interval 0, . . . , φ(n) ’ 1. Not all

n

positive integers have primitive roots ” we will see in §10.2 that the only

positive integers n for which there exists a primitive root modulo n are

n = 1, 2, 4, pe , 2pe ,

where p is an odd prime and e is a positive integer.

Exercise 2.15. Find an integer whose multiplicative order modulo 101 is

100.

Exercise 2.16. Suppose ± ∈ Z— has multiplicative order k. Show that for

n

any m ∈ Z, the multiplicative order of ±m is k/ gcd(m, k).

Exercise 2.17. Suppose ± ∈ Z— has multiplicative order k, β ∈ Z— has

n n

multiplicative order , and gcd(k, ) = 1. Show that ±β has multiplicative

order k . Hint: use the previous exercise.

28 Congruences

Exercise 2.18. Prove that for any prime p, we have

(p ’ 1)! ≡ ’1 (mod p).

Hint: using the result of Exercise 2.5, we know that the only elements of Z— p

that act as their own multiplicative inverse are [±1]n ; rearrange the terms

in the product β∈Z— β so that except for [±1]n , the terms are arranged in

p

pairs, where each pair consists of some β ∈ Z— and its multiplicative inverse.

p

2.6 Arithmetic functions and M¨bius inversion

o

A function, such as Euler™s function φ, from the positive integers into the

reals is sometimes called an arithmetic function (actually, one usually

considers complex-valued functions as well, but we shall not do so here).

An arithmetic function f is called multiplicative if f (1) = 1 and for all

positive integers n, m with gcd(n, m) = 1, we have f (nm) = f (n)f (m).

Theorem 2.12 simply says that φ is multiplicative.

In this section, we develop some of the theory of arithmetic functions that

is pertinent to number theory; however, the results in this section will play

only a very minor role in the remainder of the text.

We begin with a simple observation, which the reader may easily verify:

if f is a multiplicative function, and if n = pe1 · · · per is the

r

1

prime factorization of n, then

f (n) = f (pe1 ) · · · f (per ).

r

1

Next, we de¬ne a binary operation on arithmetic functions that has a

number of interesting properties and applications. Let f and g be arith-

metic functions. The Dirichlet product of f and g, denoted f g, is the

arithmetic function whose value at n is de¬ned by the formula

(f g)(n) := f (d)g(n/d),

d|n

the sum being over all positive divisors d of n. Another, more symmetric,

way to write this is

(f g)(n) = f (d1 )g(d2 ),

n=d1 d2

the sum being over all pairs (d1 , d2 ) of positive integers with d1 d2 = n. The

Dirichlet product is clearly commutative (i.e., f g = g f ), and is associative

2.6 Arithmetic functions and M¨bius inversion

o 29

as well, which one can see by checking that

(f (g h))(n) = f (d1 )g(d2 )h(d3 ) = ((f g) h)(n),

n=d1 d2 d3

the sum being over all triples (d1 , d2 , d3 ) of positive integers with d1 d2 d3 = n.

We now introduce three special arithmetic functions: I, J, and µ. The

function I(n) is de¬ned to be 1 when n = 1 and 0 when n > 1. The function

J(n) is de¬ned to be 1 for all n.

The M¨bius function µ is de¬ned for positive integers n as follows:

o

0 if n is divisible by a square other than 1;

µ(n) := r if n is the product of r ≥ 0 distinct primes.

(’1)

Thus, if n = pe1 · · · per is the prime factorization of n, then µ(n) = 0 if ei > 1

r

1

for some i, and otherwise, µ(n) = (’1)r . Here are some examples:

µ(1) = 1, µ(2) = ’1, µ(3) = ’1, µ(4) = 0, µ(5) = ’1, µ(6) = 1.

It is easy to see (verify) that for any arithmetic function f , we have

I f = f and (J f )(n) = f (d).

d|n

Also, the functions I, J, and µ are multiplicative (verify). A useful property

of the M¨bius function is the following:

o

Theorem 2.17. For any multiplicative function f , if n = pe1 · · · per is the

r

1

prime factorization of n, we have

µ(d)f (d) = (1 ’ f (p1 )) · · · (1 ’ f (pr )). (2.7)

d|n

In case r = 0 (i.e., n = 1), the product on the right-hand side of (2.7) is

interpreted (as usual) as 1.

Proof. The non-zero terms in the sum on the left-hand side of (2.7) are those

corresponding to divisors d of the form pi1 · · · pi , where pi1 , . . . , pi are dis-

tinct; the value contributed to the sum by such a term is (’1) f (pi1 · · · pi ) =

(’1) f (pi1 ) · · · f (pi ). These are the same as the terms in the expansion of

the product on the right-hand side of (2.7). 2

For example, suppose f (d) = 1/d in the above theorem, and let n =

pe1· · · per be the prime factorization of n. Then we obtain:

r

1

µ(d)/d = (1 ’ 1/p1 ) · · · (1 ’ 1/pr ). (2.8)

d|n

30 Congruences

As another example, suppose f = J. Then we obtain

r

(1 ’ 1),

(µ J)(n) = µ(d) =

i=1

d|n

which is 1 if n = 1, and is zero if n > 1. Thus, we have

µ J = I. (2.9)

Theorem 2.18 (M¨bius inversion formula). Let f and F be arithmetic

o