欧拉函数性质
$n = \sum_{d|n}{\phi(n)}$
每日一证 5.20
公式
欧拉函数性质
$n = \sum_{d|n}{\phi(n)}$
证明
- $[1,n]$ 中的每个数字和 $n$ 的 $gcd$ 都是确定且唯一的。
- 设 $1\le x\le n$，$(x, n) = d$，那么可以得到 $(\frac{x}{d}, \frac{n}{d})= 1$。
- 所以对于 $d$，满足 $(\frac{x}{d}, \frac{n}{d})= 1$ 的数量为不超过 $\frac{n}{d}$ 且和 $\frac{n}{d}$ 的数量，即为 $\phi(\frac{n}{d})$。
- 故问题得证。