Mobius
Function
Reporters:
Alliah Maguad
Trisha Anne Rebito
Jodale Aguirre
MOBIUS FUNCTIONS
For a positive integer n the Mobius function μ defined as:
{
1 if n=1
2
μ(n) 0 ifp /n for some prime p
(-1)k if n= p1p2…p k is the product of k distinct primes.
For example:
1. μ (6) = μ (21x31)
=(-1)1+1
= (-1)2
=1
2. μ (9) = μ (3²)
=0
Theorem 1:
Mobius function μ (n) is multiplicative i.e., μ (mn) = μ (m) μ (n)
, m and n are relatively prime.
Proof: We consider the following three conditions:
(i) m = 1 then μ(mn) = μ(1.η)
= μ(n)
= 1. μ(n)
= μ(m) μ(n).
Thus, the given result is true for m = 1.
(ii) m is divisible by p², p is a prime. In this case (m) = 0 and
μ(mn) = 0. Therefore
μ(mn) = μ(m)·μ(n)
(iii) m = p1p2 … Pk1
n = q1q2 … qk2
where pi’s are different from qi.
In this case
μ(mn) = (-1)k1 +k2
= (-1) k1 (-1) k2
= μ (m) μ (n)
Theorem 2: Let n be a positive integer.
∑
d/n
μ(d) = {01 ifif nn=1>1
Example:
1. let n = 12
2. let n = 39
Example:
1. Let n = 12
12 = {1, 2, 3, 4, 6, 12}
∑μ(d) = ∑μ(d)
d/n d/12
=
μ(1) + μ(2) + μ(3) + μ(4) + μ(6) + μ(12)
=1-1-1+0+1+0
=0
∑μ(d) = 0, n = 12 > 1
d/12
2. Let n = 39
39= {1,3,13,39}
∑μ(d) = ∑μ(d)
d/n d/39
=μ(1) + μ(3) + μ(13) + μ(39)
= 1-1-1+1
=0
∑μ(d) = 0, n = 39 > 1
d/39
If n > 1 then we can write
Theorem 3: (Mobius Inversion Formula)
Let F(n) = ∑d/nf(d)
Then f(n) =
∑d/n
n
μ(d)F( ) =
d ∑d/n
μ ()
n
d
F(d)
Proof: We have
∑d/nμ(d)F ()
n
d
= ∑d/n
[μ(d)∑ f(c)] n
c/( )
d
=∑d/n
[∑ μ(d)f(c)]
n
c/( )
d
=∑c/n
[∑ n
d/( )
c
f(c)μ(d)
]
[ d c c n
∴ and ⇔ and d/( )
n n n
d
c
]
=∑c/n
[f(c)∑ nμ(d)
d/( )
c
]
=∑c=nf(c).1
=f(n)
Theorem 4: If F(n) is a multiplicative function and F(n)=
∑d/nf(d)
then f is also multiplicative.
Proof: Let m and n be relatively prime. Then any divisor
d of mn can be written uniquely as d = d1d2, where
d₁/m and d₂/n and (d₁, d₂) = 1.
Now by inversion formula we have,
a1 a2 ak
Theorem 5: if n = p1 p2 ….pk then
∑d/n|μ(d)| = 2
k
Proof: For every divisor d for which µ(d) ≠ 0 we have |
µ(d) | = 1. Therefore, by definition of Mobius function
and the number of such divisors is given by
k
1+( ) +
1
k
2()
+…+
k
k ()
= (1+1)k = 2k
Hence,
∑|μ(d)|
d/n
=2k.1
=2k
a1 a2 ak
Theorem 6: if n = p1 . p2 .….pk then
∑d/n
μd
d
=(1-1/p1)(1-1/p2)… 1-
1
pk ( )
1
Proof: Let f(n) = . Then we have
n
∑μ(d)f(d)
d/n
∑d/nμ d/d
Example 1: For each positive integer n, show that
μ(n) μ(n + 1) μ(n + 2) μ(n + 3) = 0.
Solution: We have,
μ(n) μ(n + 1) μ(n + 2) μ(n + 3) =
μ[n(n+1)(n+2)(n+3)].
[By multiplicative property
Now for each value of n there will be two even
numbers and two odd numbers among the four factors
of right hand side. Therefore there will be one factor 22
in the product. Hence, the Mobius function will be zero
because µ(22) = 0.
Example 2: Find a positive integer n such that μ(n) +
μ(n + 1) + μ(n+2)-3
Solution: We have
μ(33) = μ (3 • 11) = (-1)² = 1
μ(34) = μ (2 • 17) = (-1)² = 1
μ(35) = μ (5 • 7) = (-1)² = 1
Thus, μ(33) + μ(34) + μ(35) = 3.
Therefore n should be equal to 33.
Similarly,
μ(85) = μ(5.17) = (-1)² = 1
μ(86) = μ (2.43) = (-1)² = 1
μ(87) = μ(3.29) = (-1)² = 1.
Thus, μ(85) + μ(86) + μ(87) = 3. Therefore n = 85.
Also
μ(93) = μ(3.31) = (-1)²=1
μ(94) = μ(2.47) = (-1)² = 1
μ(95) = μ(5.19) = (-1)² = 1.
Thus, μ(93) + μ (94) + μ(95) = 3. Therefore, n = 93.
Thus the result is true for n = m + 1. Hence by
mathematical induction the will be true for all
values of n ≥ 3.
Exercises:
Find the following:
1. μ(20)
Solution:
20 =2² x 5
μ(20) = 0
2. μ(98)
Solution:
98 = 2 x 7²
μ(98) = 0
Assignment.
1. Find a positive integer n such that μ(n) + μ(n+1)+
μ(n+2) = 3.
Solution:
μ(33) = μ(3.11) = (-1)2 = 1
μ(34) = μ(2.17) = (-1)2 = 1
μ(35) = μ(5.7) = (-1)2 = 1
μ(33) + μ(34) + μ(35) = 3
2. Find the following:
a. μ(102)
Solution:
102 =2 x 3 x 17
μ(102) = -1
b. μ(105)
Solution:
105 = 3 x 5 x 7
μ(105) = - 1
c. μ(2310)
Solution:
2310 = 2 x 3 x 5 x 7 x 11
μ(2310) = - 1
d. μ(p³)
Solution:
p = p² x p¹
μ(p³) = 0
Source: Number Theory By Hari Kishan, 6.3 Mobius Function
