第七次作业

liblaf4/2/25About 3 min

1. (3.76.)

[!QUESTION]
试证欧拉函数 $ϕ (n) = n \sum_{d | n} \frac{μ (d)}{d}$ , 其中求和是对 $n$ 的所有除数, 包括 $1$ 和 $n$ 进行的.

欧拉函数 $ϕ (n)$ 表示 $1$ 到 $n$ 中与 $n$ 互质的数的个数. 设 $n$ 的质因数为 $p_{1}, p_{2}, \dots, p_{k}$ , 根据容斥原理:

ϕ (n) = n - \sum \frac{n}{p_{i}} + \sum \frac{n}{p_{i} p_{j}} - \dots + (- 1)^{k} \frac{n}{p_{1} p_{2} \dots p_{k}}

莫比乌斯函数 $μ (d)$ 定义为:

$μ (d) = 0$ 若 $d$ 有平方因子;
$μ (d) = (- 1)^{m}$ 若 $d$ 是 $m$ 个不同质数的乘积.
结合容斥原理，上述求和可统一表示为： $ϕ (n) = \sum_{d | n} μ (d) \cdot \frac{n}{d}$

其 中, 当 $ d $ 非 平 方 自 由 时, $ μ (d) = 0 $, 因 此 求 和 只 需 考 虑 $ n $ 的 平 方 自 由 因 子 . 整 理 形 式 即 得 :

\phi(n) = n \sum_{d | n} \frac{\mu(d)}{d}

## 2. (3.75.) > [!QUESTION] > 已知 $n$ 是正整数, $d_1 = 1, d_2, d_3, \dots, d_r = n$ 是 $n$ 的除数, 即 $d_i | n, i = 1, 2, \dots, r$, 试证 $\sum_{d_i} \phi(d_i) = n$. 考虑集合 $S = \{1, 2, \dots, n\}$. 将 $S$ 中的每个元素 $m$ 按 $\gcd(m, n)$ 的值进行分类. 由于 $\gcd(m, n)$ 必为 $n$ 的某个除数 $d$, 因此可将 $S$ 划分为若干不相交的子集, 每个子集对应一个 $d | n$. 对于每个除数 $d$, 设子集 $S_d = \{ m \in S \mid \gcd(m, n) = d \}$. 令 $m = d \cdot k$, 则 $\gcd(d \cdot k, n) = d \cdot \gcd(k, n/d)$, 为使 $\gcd(m, n) = d$, 需满足 $\gcd(k, n / d) = 1$. 此时, $k$ 的取值范围为 $1 \leqslant k \leqslant n / d$, 且与 $n / d$ 互质的 $k$ 的个数为 $\phi(n / d)$. 因此, $|S_d| = \phi(n / d)$. 由于所有子集 $S_d$ 互不相交且覆盖 $S$, 故

n = \sum_{d \mid n} |S_d| = \sum_{d \mid n} \phi\left(\frac{n}{d}\right)

注 意 到 当 $ d $ 取 遍 $ n $ 的 所 有 除 数 时, $ n / d $ 也 取 遍 $ n $ 的 所 有 除 数, 因 此

\sum_{d \mid n} \phi\left(\frac{n}{d}\right) = \sum_{d \mid n} \phi(d)

结 合 上 式 即 得

\sum_{d \mid n} \phi(d) = n

## 3. (3.77.) > [!QUESTION] > 设 $f$ 满足 $f(m n) = f(m) f(n), g(n) = \sum_{d | n} f(d)$, 其中 $m$ 和 $n$ 互质, 试证: $g(m n) = g(m) g(n)$. 由于 $m$ 和 $n$ 互质, $m n$ 的每个因数 $d$ 可唯一表示为 $d = a b$, 其中 $a | m$, $b | n$, 且 $a$ 和 $b$ 互质. 对于每个 $d = a b$, 由 $f$ 的积性 ($a$ 和 $b$ 互质), 有:

f(a b) = f(a) f(b)

将 $ g (m n) $ 的 求 和 分 解 为 对 $ a | m $ 和 $ b | n $ 的 双 重 求 和 :

g(m n) = \sum_{d | m n} f(d) = \sum_{a | m} \sum_{b | n} f(a b)

代 入 $ f (a b) = f (a) f (b) $, 得 到 :

g(m n) = \sum_{a | m} \sum_{b | n} f(a) f(b) = \left( \sum_{a | m} f(a) \right) \cdot \left( \sum_{b | n} f(b) \right)

根 据 $ g $ 的 定 义, 直 接 得 出 :

g(m n) = g(m) \cdot g(n)

综上，当 $m$ 和 $n$ 互质时, $g(m n) = g(m) g(n)$ 成立. ## 4. (3.78.) > [!QUESTION] > $n$ 是正整数, $n$ 的正除数的数目用 $\tau(n)$ 来表示, 试证: $\sum_{d | n} \mu(d) \tau(\frac{n}{d}) = 1$. 设函数 $G(n) = 1$ 对所有 $n \geqslant 1$ 成立, 并定义 $F(n) = \sum_{d | n} G(d)$. 由于 $G(d) \equiv 1$, 则:

F(n) = \sum_{d | n} 1 = \tau(n)

即 $ F (n) $ 为 $ n $ 的 除 数 函 数 $ τ (n) $ . 根 据 M ö b i u s 反 演 定 理, 若 $ F (n) = \sum_{d | n} G (d) $, 则 :

G(n) = \sum_{d | n} \mu(d) F\left(\frac{n}{d}\right)

将 $ F (n) = τ (n) $ 代 入 得 :

G(n) = \sum_{d | n} \mu(d) \tau\left(\frac{n}{d}\right)

由 于 $ G (n) \equiv 1 $, 因 此 :

\sum_{d | n} \mu(d) \tau\left(\frac{n}{d}\right) = 1