Learning Mobius Function

MOBIUS FUNCTION (source)

The classical Möbius function μ(n) is an important multiplicative function in number theory and combinatorics. The German mathematician August Ferdinand Möbius introduced it in 1832.

Definition:  μ(n) is defined for all positive integers n and has its values in {−1, 0, 1} depending on the factorization of n into prime factors. It is defined as follows:

Please take time to watch the video.

http://www.youtube.com/watch?v=zlRm1Lnz6fg

Thus for some p, μ(p) = -1; μ(p^k) = 0, for k ≥ 2.

Theorem 1:  The function µ is a multiplicative function.

Proof:  We want to show that µ(mn) =  µ(m)µ(n), whenever m and n are relatively prime.  

 

a. If either p2 / m or p² / n, p a prime, then p² / mn.  Therefore, µ(mn) = 0 = µ(m)µ(n).

b. Let m and n be square-free, and we let m = p₁p₂…p_r and n = q₁q₂…q_s, with all the primes p_i and q_j being distinct.  Then µ (m) = (- 1)^r and µ(n) = (-1)^s, and

                        µ(mn) = µ(p₁…p_rq₁…q_s)

                                    = (-1)^r+s

                                    = (-1)^r (-1)^s

                                    = µ(m)µ(n)

c. Let at least one of the integers m or n be 1, m = 1.  Then µ(m) = 1 and

                        µ(mn) = µ(n) = 1 ∙ µ(n) = µ(m)µ(n)

Theorem 2:  For each positive integer n ≥ 1,

where d runs through the positive divisors of n

Proof:  If n = 1, then

                        ∑ µ (d) =  µ(1) = 1

                       dI1        

For n > 1, set

                        g(n) = ∑ µ (d)

                                 dIn

Consider g(n) for some power of a prime say n = p^k.  The positive divisors of p^k are just the k+1 integers 1, p, p²,…,p^k, so that,

                                g(p^k) = ∑ µ (d) = µ(1) + µ(p) + µ(p²) + …+µ(p^k)

                                             dIp^k

                                                  = µ(1) + µ(p) = 1 + (-1) = 0

Example: Let n = 10, the divisors on n are 1, 2, 5, 10

                        ∑ µ(d) = µ(1) + µ(2) + µ(5) + µ(10)

                     dI10     

                                                = 1 + (-1) + (-1) + 1 = 0

Exercise:

(a)  Compute the values of the Mobius function μ(n) for n = 1, ・ ・ ・ , 20

A quotation to live by...hope I taught something for you.