欧拉函数的一般公式是什么？

适用条件

• $n$ 是大于 1 的正整数。
• $p_1, \ldots, p_m$ 是 $n$ 的所有不同质因数。

理解与推导

1. 从 $n$ 的质因数分解开始：$n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}$。
2. 利用 $\varphi$ 的积性写出 $\varphi(n) = \varphi(p_1^{k_1}) \varphi(p_2^{k_2}) \cdots \varphi(p_m^{k_m})$。
3. 对每个因子代入质数幂公式 $\varphi(p^k) = p^k - p^{k-1}$。
4. 从每一项中提取 $p_i^{k_i}$：$p_i^{k_i} - p_i^{k_i-1} = p_i^{k_i}(1 - 1/p_i)$。
5. 将所有提取后的项相乘：$\varphi(n) = (p_1^{k_1} \cdots p_m^{k_m}) \prod_{i=1}^{m} (1 - 1/p_i)$。
6. 认识到 $p_1^{k_1} \cdots p_m^{k_m} = n$，得到最终公式 $\varphi(n) = n \prod_{i=1}^{m} (1 - 1/p_i)$。
7. 使用乘积符号压缩乘积。

例子

对于 $n = 100$，不同的质因数是 2 和 5。使用公式：$\varphi(100) = 100 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{5}\right) = 100 \cdot \frac{1}{2} \cdot \frac{4}{5} = 40$。

容易误解的地方

• 在乘积中包含重复的质因数（乘积是针对不同的质因数）。
• 忘记在公式开头乘以 $n$。
• 将一般公式与特定的质数幂公式 $\varphi(p^k) = p^k - p^{k-1}$ 混淆。

观看对应讲解

继续追问

• 为什么 $φ(p_1^{k_1}p_2^{k_2}\cdot \cdot \cdot p_m^{k_m})$ 可以拆分为 $φ(p_1^{k_1})φ(p_2^{k_2})\cdot \cdot \cdot φ(p_m^{k_m})$？
• 如何推导 $φ(p^k) = p^k - p^{k-1}$？
• 对于 $t>0$，上限 u=sqrt(t) 的导数是什么？