每日一证 5.20

欧拉函数性质

$n = sum_{d|n}{phi(n)}$

• $[1,n]$ 中的每个数字和 $n$ 的 $gcd$ 都是确定且唯一的。
• 设 $1le xle 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})$。
• 故问题得证。