莫比乌斯函数 μ(n)：揭开-1,0,1背后的秘密

1. 一个“魔术”般的函数

在数论中，有一个函数取值非常特殊：它只可能是 -1、0 或 1。它就是莫比乌斯函数，记作 $\mu(n)$ 。虽然取值简单，但它却是解开许多数论谜题的钥匙。就像扑克牌中的大小王，看起来不起眼，却能改变整局游戏。

想象你有一盒不同颜色的积木，每个积木代表一个质数。如果一个数是“无平方因子”的（即每个质因数只出现一次），那么它就像一袋积木中每种颜色只有一块；如果有某种颜色有两块以上，那就有“重复”了。莫比乌斯函数就像一位裁判：对“干净”的数（无平方因子）根据颜色种数的奇偶给出 +1 或 -1 的分数，对“重复”的数直接给 0 分。这个简单的打分规则，在数论中却是一个强大的“筛选器”。

n	质因数分解	μ(n)	解释
1	1	1	空集，偶数个因子（0个）
2	2	-1	1个质因子，奇数
3	3	-1	1个质因子，奇数
4	2²	0	有平方因子
5	5	-1	1个质因子，奇数
6	2×3	1	2个质因子，偶数
7	7	-1	1个质因子，奇数
8	2³	0	有平方因子（2²）
9	3²	0	有平方因子
10	2×5	1	2个质因子，偶数

3. 莫比乌斯函数的关键性质

最重要的性质是：

\sum_{d|n} \mu(d) = \begin{cases} 1, & n = 1,\\ 0, & n > 1. \end{cases}

这相当于说：对所有正因子 $d$ 的莫比乌斯函数值求和，只有当 $n=1$ 时和为1，否则为0。这个性质是莫比乌斯反演的核心。

3.1 用生活例子理解

想象你有一张“因子派对”的邀请名单：对于一个数 n，它的所有正因子 d 都会来参加。莫比乌斯函数值就像是每个因子 d 的“门票数”（1 或 -1 或 0）。结果发现：如果 n=1，所有门票加起来正好是 1 元；如果 n>1，不管怎么加，总是 0 元。这就像一个奇妙的“平衡器”——除了 1，其他所有数的因子贡献刚好正负抵消。

拿 n=6 举例：6 的正因子有 1,2,3,6。
μ(1)=1，μ(2)=-1，μ(3)=-1，μ(6)=1，加起来：1 + (-1) + (-1) + 1 = 0。
再试试 n=12：因子有 1,2,3,4,6,12。
μ(1)=1，μ(2)=-1，μ(3)=-1，μ(4)=0，μ(6)=1，μ(12)=0，和 = 1-1-1+0+1+0 = 0。
n=1 时只有因子 1，和就是 1。完美符合！

3.3 证明（可跳过）

设 $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ 。由于有平方因子的 $d$ 会使 $\mu(d)=0$ ，我们只需要考虑那些无平方因子的 $d$ 。而这样的 $d$ 恰好是由 $n$ 的不同质因子组成的子集。设 $r$ 为质因子个数，则恰有 $\binom{k}{t}$ 个 $d$ 包含 $t$ 个不同质因子，每个贡献 $(-1)^t$ 。所以

\sum_{d|n} \mu(d) = \sum_{t=0}^{k} \binom{k}{t} (-1)^t = (1-1)^k = 0^k.

当 $k=0$ 即 $n=1$ 时，值为1；否则 $k>0$ 时值为0。

这个性质就像是一个“筛选器”：当我们把莫比乌斯函数加到所有因子求和上，它会神奇地留下 $n=1$ 的情况，其他全部过滤掉。

4. 莫比乌斯函数是积性函数

可以证明：若 $\gcd(a,b)=1$ ，则 $\mu(ab) = \mu(a)\mu(b)$ 。因为互质的两个数不会有公共质因子，所以 ab 是否有平方因子、质因子个数都是 a 和 b 对应情况相乘。例如 a=2，b=3， $\mu(2)=-1$ ， $\mu(3)=-1$ ，乘积为1，而 $\mu(6)=1$ ，满足。如果 a=2，b=4，它们不互质（有公因子2），所以不能直接用积性——实际上 $\mu(2)=-1$ ， $\mu(4)=0$ ，乘积=0，而 $\mu(8)=0$ ，虽然结果看起来相同（0），但这是巧合，不能依赖。

积性让我们可以像搭积木一样，把大数的 μ 值分解成小互质数的 μ 值相乘。比如要算 μ(30)，因为 30=2×3×5，且两两互质，所以 μ(30)=μ(2)×μ(3)×μ(5)=(-1)×(-1)×(-1)=-1。非常方便！

5. 新手容易犯的错误

忽略 n=1：很多初学者认为 μ(1) 应该是 0 或 -1，但定义明确给出 μ(1)=1。记住 1 是“空袋”，偶数个质因子（0个），所以是 1。
误判平方因子：比如 n=8=2³，有平方因子 2²，所以 μ(8)=0，不要因为指数是奇数就误以为无平方因子。只要任意质因子的指数≥2，就一定有平方因子。
混淆不同质因子个数k与指数：μ(n) 只关心不同质因子的个数，不关心指数大小（除非指数≥2导致 μ=0）。比如 n=12=2²×3，不同质因子有2和3共2个，但因为2的指数≥2，所以 μ=0。
在编程中忘记处理平方因子：分解质因数时，一旦发现某个质因子的指数≥2，应立即返回0。
线性筛中错误设置 mu[i*p]：当 i%p==0 时，i 和 p 不是互质的，此时 ip 有 p² 因子，所以 mu[ip] 应为 0；不能直接用积性。

6. 编程计算 μ(n)

6.1 计算单个 n 的 μ 值

计算单个 n 的 μ 值很容易：先分解质因数，判断是否有平方因子，然后数不同质因子个数。

C++ 实现

#include <iostream>
#include <cmath>
using namespace std;

// 返回 n 的莫比乌斯函数值
int mobius(long long n) {
    if (n == 1) return 1;
    int cnt = 0;          // 不同质因子个数
    long long temp = n;
    for (long long i = 2; i * i <= temp; i++) {
        if (temp % i == 0) {
            // 找到质因子 i
            int exponent = 0;
            while (temp % i == 0) {
                temp /= i;
                exponent++;
            }
            if (exponent >= 2) {
                // 有平方因子，直接返回0
                return 0;
            }
            cnt++;   // 不同质因子个数加1
        }
    }
    // 如果最后剩下大于1的质因子
    if (temp > 1) {
        cnt++;
    }
    // 根据 cnt 的奇偶性返回 ±1
    return (cnt % 2 == 0) ? 1 : -1;
}

int main() {
    long long n;
    cout << "请输入一个正整数 n: ";
    cin >> n;
    cout << "μ(" << n << ") = " << mobius(n) << endl;
    return 0;
}

Python 实现

def mobius(n):
    """返回 n 的莫比乌斯函数值"""
    if n == 1:
        return 1
    cnt = 0          # 不同质因子个数
    temp = n
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            exponent = 0
            while temp % p == 0:
                temp //= p
                exponent += 1
            if exponent >= 2:
                return 0          # 有平方因子
            cnt += 1
        p += 1
    if temp > 1:     # 剩余一个大于 sqrt(n) 的质因子
        cnt += 1
    return 1 if cnt % 2 == 0 else -1

# 测试
n = int(input("请输入一个正整数 n: "))
print(f"μ({n}) = {mobius(n)}")

6.2 完整可运行示例：打印 1 到 20 的 μ 值

下面是一个完整的 Python 程序，它计算并打印 1 到 20 的莫比乌斯函数值，让你直观感受：

def mobius(n):
    """返回 n 的莫比乌斯函数值"""
    if n == 1:
        return 1
    cnt = 0
    temp = n
    p = 2
    while p * p <= temp:
        if temp % p == 0:
            exp = 0
            while temp % p == 0:
                temp //= p
                exp += 1
            if exp >= 2:
                return 0
            cnt += 1
        p += 1
    if temp > 1:
        cnt += 1
    return 1 if cnt % 2 == 0 else -1

print("前 20 个莫比乌斯函数值：")
for i in range(1, 21):
    print(f"μ({i}) = {mobius(i)}")

运行结果：

前 20 个莫比乌斯函数值：
μ(1) = 1
μ(2) = -1
μ(3) = -1
μ(4) = 0
μ(5) = -1
μ(6) = 1
μ(7) = -1
μ(8) = 0
μ(9) = 0
μ(10) = 1
μ(11) = -1
μ(12) = 0
μ(13) = -1
μ(14) = 1
μ(15) = 1
μ(16) = 0
μ(17) = -1
μ(18) = 0
μ(19) = -1
μ(20) = 0

观察一下，有没有发现质数的 μ 值都是 -1（除了 1）？没错，因为质数只有一个质因子，是奇数个。而完全平方数（4,9,16）都是 0。两个不同质因子乘积（6,10,14,15）都是 1，因为 2 个是偶数。三个不同质因子的乘积（30 不在前 20）会是 -1。

7. 用线性筛求莫比乌斯函数值

当需要计算 1 到 N 所有 μ 值时，可以用线性筛（欧拉筛）同时计算。思路：每个数的最小质因子已知，利用莫比乌斯函数的积性，可以递推。

7.1 C++ 线性筛求 μ

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1000000;
int mu[MAXN + 1];          // 存储莫比乌斯函数值
vector<int> primes;
bool is_composite[MAXN + 1] = {false};

void compute_mobius(int n) {
    mu[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!is_composite[i]) {
            primes.push_back(i);
            mu[i] = -1;          // 质数只有一个质因子，所以 μ = -1
        }
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            int p = primes[j];
            is_composite[i * p] = true;
            if (i % p == 0) {
                // p 是 i 的最小质因子，那么 i*p 含有 p 的平方因子
                // 根据定义，有平方因子的数 μ = 0
                mu[i * p] = 0;
                break;   // 关键：线性筛保证了每个合数只被最小质因子筛一次
            } else {
                // p 与 i 互质，利用积性
                mu[i * p] = mu[i] * mu[p];   // mu[p] = -1
            }
        }
    }
}

int main() {
    int N;
    cout << "请输入 N: ";
    cin >> N;
    compute_mobius(N);
    cout << "前10个莫比乌斯函数值:" << endl;
    for (int i = 1; i <= min(N, 10); i++) {
        cout << "μ(" << i << ") = " << mu[i] << endl;
    }
    return 0;
}

7.2 Python 线性筛求 μ

MAXN = 1000000
mu = [0] * (MAXN + 1)
primes = []
is_composite = [False] * (MAXN + 1)

def compute_mobius(n):
    mu[1] = 1
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            mu[i] = -1          # 质数 μ = -1
        for p in primes:
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                mu[i * p] = 0   # 有平方因子
                break
            else:
                mu[i * p] = mu[i] * mu[p]   # 积性

N = int(input("请输入 N: "))
compute_mobius(N)
print("前10个莫比乌斯函数值:")
for i in range(1, min(N, 10) + 1):
    print(f"μ({i}) = {mu[i]}")

线性筛的精髓在于每个合数只被它最小的质因子筛掉一次。当 i % p == 0 时，p 是 i 的最小质因子，此时 i * p 中 p 的指数至少为 2，所以 μ=0，然后 break 防止重复标记。否则 p 与 i 互质，利用积性直接把两个 μ 相乘。

8. 总结

莫比乌斯函数虽然取值简单，但它的性质 $\sum_{d|n} \mu(d) = [n=1]$ 是数论中重要的“筛选工具”。它是积性函数，可以方便地用线性筛批量计算。掌握了它，你就能进入莫比乌斯反演的世界，解决许多和因子有关的求和问题。

想一想：你能用这个性质证明，对于任意正整数 n，所有与 n 互质的数的个数等于 $\sum_{d|n} \mu(d) \cdot \lfloor n/d \rfloor$ 吗？（提示：利用互质数的计数公式 $\varphi(n) = n \sum_{d|n} \frac{\mu(d)}{d}$ ，这个公式就是莫比乌斯反演的结果。）

下一步可以学习

欧拉函数 φ(n)：它与莫比乌斯函数有密切关系，上面提到的公式就是它们的“桥梁”。
莫比乌斯反演：从 $\mu$ 的性质出发，可以推导出一般的反演公式，用来化简复杂的求和式。
狄利克雷卷积：理解莫比乌斯函数和常数函数 1、单位函数等之间的关系，更系统地掌握数论函数。

莫比乌斯函数就像一把“瑞士军刀”，虽然小巧，但功能强大。以后遇到涉及因子求和的问题，不妨想想这位“-1,0,1”的魔术师！

莫比乌斯函数 μ(n) 的定义与性质