Number Theory: An Introduction to Mathematics

156 III More on Divisibility

By Proposition II.24, Euler’sφ-function satisfiesi∗φ=j. Thusφ=i−^1 ∗j,and
Propositions 26 and 27 provide a new proof that Euler’sφ-function is multiplicative.
Since

τ∗φ=i∗i∗φ=i∗j=σ,

we also obtain the new relation

σ(n)=

∑

d|n

τ(n/d)φ(d).

TheMobius function ̈ μ:N→Cis defined to be the Dirichlet inversei−^1. Thus
μ∗i=δor, in other words,
∑

d|n

μ(d)=1 or 0 according asn=1orn> 1.

Instead of this inductive definition,we may explicitly characterize the M ̈obius
function in the following way:

Proposition 28For any n∈N,

μ(n)=

⎧

⎪⎨

⎪⎩

1 if n= 1 ,

(− 1 )s if n is a product of s distinct primes,

0 if n is divisible by the square of a prime.

Proof It is trivial thatμ( 1 )=1. Supposepis prime andα∈N. Since the divisors of
pαare 1,p,...,pα,wehave

μ( 1 )+μ(p)+···+μ(pα)= 0.

Since this holds for allα ∈ N, it follows thatμ(p) =−μ( 1 ) =−1, whereas
μ(pα)=0ifα>1. Since the M ̈obius function is multiplicative, by Proposition 27,
the general formula follows.

The function defined by the statement of Proposition 28 had already appeared in
work of Euler (1748), but M ̈obius (1832) discovered the basic property which we have
adopted as a definition. From this property we can easily derive theM ̈obius inversion
formula:

Proposition 29For any function f:N→C,iffˆ:N→Cis defined by

fˆ(n)=

∑

d|n

f(d),

then

f(n)=

∑

d|n

fˆ(d)μ(n/d)=

∑

d|n

fˆ(n/d)μ(d).

Furthermore, for any functionfˆ:N→C, there is a unique function f:N→C
such thatfˆ(n)=

∑

d|nf(d)for every n∈N.