莫比烏斯反演

數學術語

莫比烏斯反演是數論數學中很重要的內容,可以用於解決很多組合數學的問題。

意思就是先給出一個函數F(n),然後再由F(n)定義一個新函數G(n),其中 G(n)=sigma(F(d)) (其中d被“包含”於n) ,現在不知道F(n)的值,卻知道G(n),接著就可以通過反演由G(n)反向得到F(n)。

引入


莫比烏斯反演是數論中的重要內容,在許多情況下能夠簡化運算。考慮以下求和函數:
需要找到和之間的關係。從和函數定義當中,可以知道:
那麼:
從中,可以看出,若(為質數)那麼,所以,.
如果要讓函數滿足:
那麼通過以上推導可以知道,所以作出以下猜測:

定理


設和是定義在正整數集合上的兩個函數,定義如下。
若函數滿足:
則有

定理證明


充分性證明:
考慮到:
因此
必要性證明:
考慮到:
因此

莫比烏斯函數


定義當時,
當(為不同的質數,且次數都為1),
其餘情況
注意,函數也為積性函數。證明略。

性質


性質一(莫比烏斯反演公式):
性質二:μ(n)是積性函數
性質三:設f是算術函數,它的和函數是積性函數,那麼f也是積性函數。